693. 交替位二进制数

🟢   🔖  位运算  🔗 力扣 LeetCode

题目

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 <= 2^31 - 1

题目大意

给定一个正整数，检查它的二进制表示是否总是 0、1 交替出现：换句话说，就是二进制表示中相邻两位的数字永不相同。

示例 1：

输入： n = 5

输出： true

解释： 5 的二进制表示是：101

示例 2：

输入： n = 7

输出： false

解释： 7 的二进制表示是：111.

示例 3：

输入： n = 11

输出： false

解释： 11 的二进制表示是：1011.

提示：

• 1 <= n <= 2^31 - 1

解题思路

1. 右移与异或：

• 如果一个数的二进制表示交替出现 0 和 1，则相邻位的值总是不相同。例如：
  • 5 的二进制是 101，满足交替。
  • 7 的二进制是 111，不满足交替。
• 对于交替的二进制数，将其右移一位后与原数进行异或操作，结果的二进制表示应全为 1。例如：
  • 101 右移一位变为 10，异或得到 101 ^ 010 = 111。
• 通过 x = n ^ (n >> 1)，可以判断 n 是否满足交替位条件，其中 n >> 1 表示将 n 的二进制表示右移一位。

2. 全为 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的个数	[✓]	位运算 分治	🟢	🀄️ 🔗