Easy

题目描述

给定一个正整数，检查它是否为交替位二进制数：也就是说，其二进制数相邻的两个位数永不相等。

示例 1:

输入：n = 5
输出：true
解释：5 的二进制表示是：101

示例 2:

输入：n = 7
输出：false
解释：7 的二进制表示是：111

示例 3:

输入：n = 11
输出：false
解释：11 的二进制表示是：1011

约束条件：

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

解题思路

这道题要求判断一个数的二进制表示是否为交替位（相邻位不同）。有两种主要思路：

方法一：逐位检查（推荐） 最直观的方法是检查每相邻两位是否不同。我们可以用位运算获取最后一位，然后右移继续检查。具体步骤：

  1. 获取当前最低位 n & 1
  2. 将 n 右移一位
  3. 检查新的最低位是否与之前的位不同
  4. 重复直到 n 为 0

方法二：位运算技巧 利用交替位二进制数的特性，如果一个数是交替位的，那么：

  • n ^ (n >> 1) 会产生全为 1 的结果
  • 而全为 1 的数加 1 后会变成 10...0 的形式
  • 这样 (n ^ (n >> 1)) & ((n ^ (n >> 1)) + 1) 应该为 0

两种方法时间复杂度都是 O(log n)，但方法一更容易理解，方法二更巧妙。

代码实现

class Solution {
public:
    bool hasAlternatingBits(int n) {
        int prev = n & 1;
        n >>= 1;
        while (n > 0) {
            int curr = n & 1;
            if (curr == prev) {
                return false;
            }
            prev = curr;
            n >>= 1;
        }
        return true;
    }
};

class Solution:
    def hasAlternatingBits(self, n: int) -> bool:
        prev = n & 1
        n >>= 1
        while n > 0:
            curr = n & 1
            if curr == prev:
                return False
            prev = curr
            n >>= 1
        return True

public class Solution {
    public bool HasAlternatingBits(int n) {
        int prev = n & 1;
        n >>= 1;
        while (n > 0) {
            int curr = n & 1;
            if (curr == prev) {
                return false;
            }
            prev = curr;
            n >>= 1;
        }
        return true;
    }
}

var hasAlternatingBits = function(n) {
    let prev = n & 1;
    n >>= 1;
    
    while (n > 0) {
        let curr = n & 1;
        if (curr === prev) {
            return false;
        }
        prev = curr;
        n >>= 1;
    }
    
    return true;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型大小说明
时间复杂度O(log n)需要检查数字二进制表示的每一位
空间复杂度O(1)只使用常数级额外空间

相关题目