693. 交替位二进制数
693. 交替位二进制数
题目
Given a positive integer, check whether it has alternating bits: namely, if two adjacent bits will always have different values.
Example 1:
Input: n = 5
Output: true
Explanation: The binary representation of 5 is: 101
Example 2:
Input: n = 7
Output: false
Explanation: The binary representation of 7 is: 111.
Example 3:
Input: n = 11
Output: false
Explanation: The binary representation of 11 is: 1011.
Constraints:
1 <= n <= 231 - 1
题目大意
给定一个正整数,检查它的二进制表示是否总是 0、1 交替出现:换句话说,就是二进制表示中相邻两位的数字永不相同。
示例 1:
输入: n = 5
输出: true
解释: 5 的二进制表示是:101
示例 2:
输入: n = 7
输出: false
解释: 7 的二进制表示是:111.
示例 3:
输入: n = 11
输出: false
解释: 11 的二进制表示是:1011.
提示:
1 <= n <= 231 - 1
解题思路
- 右移与异或:
- 如果一个数的二进制表示交替出现
0
和1
,则相邻位的值总是不相同。例如:5
的二进制是101
,满足交替。7
的二进制是111
,不满足交替。
- 对于交替的二进制数,将其右移一位后与原数进行异或操作,结果的二进制表示应全为
1
。例如:101
右移一位变为10
,异或得到101 ^ 010 = 111
。
- 通过
x = n ^ (n >> 1)
,可以判断n
是否满足交替位条件,其中n >> 1
表示将n
的二进制表示右移一位。
- 全为 1 的检查:
- 如果一个数的二进制表示全为
1
,则该数与其加1
的结果按位与必为0
。例如:7
(111
) 和7 + 1
(1000
) 满足111 & 1000 = 0
。
- 因此,可以通过检查
x & (x + 1) === 0
来判断x
是否全为1
。- 若条件成立,则原数满足交替位条件,返回
true
。
- 若条件成立,则原数满足交替位条件,返回
复杂度分析
- 时间复杂度:
O(1)
,计算异或和位运算只需要常数时间。 - 空间复杂度:
O(1)
,仅使用了常数空间。
代码
/**
* @param {number} n
* @return {boolean}
*/
var hasAlternatingBits = function (n) {
const x = n ^ (n >> 1); // 计算异或结果
return (x & (x + 1)) === 0; // 检查是否全为 1
};
相关题目
题号 | 标题 | 题解 | 标签 | 难度 | 力扣 |
---|---|---|---|---|---|
191 | 位1的个数 | [✓] | 位运算 分治 | 🟢 | 🀄️ 🔗 |