跳至主要內容

693. 交替位二进制数


693. 交替位二进制数

🟢   🔖  位运算  🔗 力扣open in new window LeetCodeopen in new window

题目

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

解题思路

  1. 右移与异或
  • 如果一个数的二进制表示交替出现 01,则相邻位的值总是不相同。例如:
    • 5 的二进制是 101,满足交替。
    • 7 的二进制是 111,不满足交替。
  • 对于交替的二进制数,将其右移一位后与原数进行异或操作,结果的二进制表示应全为 1。例如:
    • 101 右移一位变为 10,异或得到 101 ^ 010 = 111
  • 通过 x = n ^ (n >> 1),可以判断 n 是否满足交替位条件,其中 n >> 1 表示将 n 的二进制表示右移一位。
  1. 全为 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的个数[✓]位运算 分治🟢🀄️open in new window 🔗open in new window