Problem Description

In this problem, we are given a positive integer, and our task is to determine whether this number represents a binary sequence of alternating bits. In other words, we have to check if every pair of adjacent bits in the binary representation of the positive integer is different. For instance, the integer 5, which in binary is 101, has alternating bits, whereas the integer 7, which in binary is 111, does not.

Intuition

To solve this problem, the solution utilizes bitwise operations, which are perfect for manipulating binary numbers directly. Here is the intuition broken down into steps:

1. We perform an XOR operation on the number n with itself shifted one bit to the right, n >> 1. An XOR operation will give us a 1 only when the two bits being compared are different. With the shifting, every pair of adjacent bits will be compared. If n has alternating bits, then this operation should result in a binary number composed entirely of 1s.

2. Now we need to verify that after the XOR operation, the number indeed consists of all 1s. For a binary number composed entirely of 1s (let's call it m), adding one to it, m + 1, will result in a binary number with a 1 followed by 0s (because it carries over). For example, if m is 111 in binary, m + 1 would be 1000.

3. If we perform a binary AND operation between m and m + 1, it should give us 0 because there are no common 1 bits between, for example, 111 (m) and 1000 (m + 1). The code checks this with (n & (n + 1)) == 0.

Putting all this together, if the number after the XOR and shift has alternating bits, it will be a string of 1s, and applying the described AND operation will yield 0, confirming that our number n had alternating bits.

Solution Approach

The given solution's implementation uses bitwise operations, which is a common and efficient way to solve problems that involve bit manipulation due to their low-level nature and high speed of execution.

Let's walk through the code:

class Solution:
    def hasAlternatingBits(self, n: int) -> bool:
        n ^= n >> 1
        return (n & (n + 1)) == 0

1. The statement n ^= n >> 1 uses the XOR (^=) operation and the right shift operator (>>). The right shift operator moves each bit of n to the right by one position. The XOR operation then compares the original n with its shifted version; if n had alternating bits, this operation will yield a number with all 1s because the different adjacent bits (when compared with XOR) return 1.

2. After the XOR operation, the solution checks if the resulting number has all 1s. To do this, it adds 1 to the number (n + 1) and then does a bitwise AND (&) with the original number (n). If the resulting number is 0, that confirms that all the bits in n were 1, due to the fact that a binary number with all 1s plus 1 will result in a power of two, which in binary is represented as 1000...0 (a one followed by zeroes).

3. The expression (n & (n + 1)) == 0 does the final check. If it evaluates to True, then the number n originally passed in had alternating bits. If not, the bits did not alternate.

This approach cleverly leverages the characteristics of binary arithmetic to solve the problem with just two operations, highlighting the efficiency and elegance of bitwise manipulation.

Example Walkthrough

Let's use the number 10 as a small example to illustrate the solution approach. The binary representation of 10 is 1010.

Step 1: Perform an XOR between n and n >> 1

• Original n in binary: 1010
• n >> 1 (shifted to right by one): 0101
• XOR operation: n ^ (n >> 1) = 1010 ^ 0101 = 1111

After the XOR operation, the number n becomes 1111, which is composed entirely of 1s. This outcome is expected for a number with alternating bits.

Step 2: Add 1 to n and perform a bitwise AND between n and n + 1

• n: 1111
• n + 1: 10000
• AND operation: n & (n + 1) = 1111 & 10000 = 0

Step 3: Conclusion

Since n & (n + 1) equals 0, we can conclude that the original number 10 does indeed have alternating bits. The bitwise operations have confirmed that every adjacent pair of bits in the binary representation of 10 was different. The solution works as intended for the example of 10.

In the case of a number without alternating bits, these two steps would lead to a non-zero result when performing the AND operation. Therefore, the condition would not be met, and the method would correctly indicate that the number does not have alternating bits.

Solution Implementation

Time and Space Complexity

The given code is a method to check whether a number has alternating bits or not. Let's analyze the time and space complexity:

Time Complexity

The code performs the following operations:

1. n ^= n >> 1: This is a bitwise XOR operation applied to the number and its right-shifted version by one bit. It runs in O(1) time since the operation is performed on a fixed number of bits that constitutes the number n.
2. (n & (n + 1)) == 0: This operation checks if the result from the first operation+1 is a power of two which guarantees alternating bits (since it would set all bits to zero). This also runs in O(1) time for the same reason as the bitwise XOR operation.

Since both operations are constant time operations, the overall time complexity of the function is O(1).

Space Complexity

The space complexity refers to the amount of extra memory used aside from the input. In this case, the function uses a fixed amount of memory to store the results of the operations, regardless of the size of n.

There are no additional data structures used that grow with the size of the input. Therefore, the space complexity is O(1).

Learn more about how to find time and space complexity quickly using problem constraints.