leetcode
leetcode 601 ~ 650
交替位二进制数

交替位二进制数

难度:

标签:

题目描述

代码结果

运行时间: 23 ms, 内存: 16.0 MB


// Java Stream solution is not applicable in this context as streams are generally used for processing sequences of elements. However, we can still demonstrate an approach using Java Streams to manipulate bits in a functional style.
 
// This approach converts the integer to its binary string representation and checks if the bits are alternating.
import java.util.stream.IntStream;
 
public class StreamSolution {
    public boolean hasAlternatingBits(int n) {
        // Convert number to binary string
        String binaryString = Integer.toBinaryString(n);
        // Check if all adjacent characters are different
        return IntStream.range(0, binaryString.length() - 1)
                .allMatch(i -> binaryString.charAt(i) != binaryString.charAt(i + 1));
    }
}
 

解释

方法:

该题解的思路是通过位运算来判断相邻两位是否不同。首先记录最低位 pre,然后右移 n,每次取出最低位 digit 与 pre 做异或操作,如果异或结果为0,说明相邻两位相同,返回 False。每次迭代更新 pre 为当前 digit,继续右移 n 直至为0。如果遍历完整个二进制数都没有返回 False,则说明符合条件,返回 True。

时间复杂度:

O(log(n))

空间复杂度:

O(1)

代码细节讲解

🦆
为什么在比较两个相邻位的时候选择使用异或操作?这种方法如何确保能正确判断相邻位的关系?
异或操作(XOR)是一种二进制操作,当两个比较的位相同时结果为0,不同时结果为1。因此,使用异或操作可以直接判断两个相邻的位是否相同。在这个题解中,如果相邻的两位是相同的,异或的结果会是0,与期望的交替位(应该相异,即期待结果为1)不符,从而返回False。这种方法通过直接比较每一对相邻位的异或结果,确保了能有效且正确地判断二进制数是否具有交替位的特性。
🦆
在代码中,你是如何确保处理的是每一个位,特别是对于数值较大的输入?
在代码中,通过不断地右移操作(n >>= 1)和位与操作(n & 1)来逐位处理二进制数。每次右移操作将当前最低位移出,并在下一次迭代中通过位与操作取出新的最低位。这个过程会持续直到整个数为0,即所有位都已经被处理。这种方法适用于任何大小的整数,因为它按照二进制的形式逐位处理,不依赖于数值的实际大小。
🦆
如果二进制数的最高位和次高位相同,异或操作会返回什么结果?这会对算法的正确性产生什么影响?
如果二进制数的最高位和次高位相同,则它们的异或结果会是0。根据算法逻辑,如果任何一对相邻位的异或结果为0,算法将返回False。这是因为相同的结果表明它们不是交替的,这正是算法设计的核心逻辑。因此,这种情况下的异或结果直接导致算法正确地判断出二进制数不是一个交替位二进制数。
🦆
在代码运行过程中,如果输入的 n 是最小值 1,这种情况下算法的表现如何?
当输入的 n 是1时,算法首先将1的最低位存储为pre,然后将n右移变为0。由于没有更多的位可供处理(n已经变为0),循环结束。由于在整个过程中没有发现任何一对相邻位不满足交替位的条件(实际上只有一个位,没有相邻位可以比较),算法最终返回True。这表明,对于只有一个位的二进制数,算法认为其符合交替位的定义,这是合理的因为没有相邻位产生冲突。

相关问题

位1的个数

编写一个函数,输入是一个无符号整数(以二进制串的形式),返回其二进制表达式中数字位数为 '1' 的个数(也被称为汉明重量)。

 

提示:

  • 请注意,在某些语言(如 Java)中,没有无符号整数类型。在这种情况下,输入和输出都将被指定为有符号整数类型,并且不应影响您的实现,因为无论整数是有符号的还是无符号的,其内部的二进制表示形式都是相同的。
  • 在 Java 中,编译器使用二进制补码记法来表示有符号整数。因此,在 示例 3 中,输入表示有符号整数 -3

 

示例 1:

输入:n = 00000000000000000000000000001011
输出:3
解释:输入的二进制串 00000000000000000000000000001011 中,共有三位为 '1'。

示例 2:

输入:n = 00000000000000000000000010000000
输出:1
解释:输入的二进制串 00000000000000000000000010000000 中,共有一位为 '1'。

示例 3:

输入:n = 11111111111111111111111111111101
输出:31
解释:输入的二进制串 11111111111111111111111111111101 中,共有 31 位为 '1'。

 

提示:

  • 输入必须是长度为 32二进制串

 

进阶

  • 如果多次调用这个函数,你将如何优化你的算法?