Bit manipulation can often feel like magic, but it is actually one of the most efficient ways to communicate with a computer. In this guide, we will explore a clever mathematical trick to determine if a number's binary bits flip-flop between 0 and 1 without using any loops.
Problem Summary
You're given:
- A single positive integer .
Your goal:
- Return
trueif every adjacent bit in the binary representation of is different, otherwise returnfalse.
Intuition
The goal is to check for a pattern like 10101 or 01010. While we could iterate through every bit, we can use bitwise operators to solve this in constant time .
If a number has alternating bits, shifting it by two positions to the right () will align the same bits. For example, if is 10101, then is 00101. When we use the XOR () operator between these two, the bits that were the same become 0.
A more elegant approach used in the provided solution involves creating a mask. If we XOR with its own bit-shifted version, we should ideally get a sequence of all 1s (like 1111). A property of a sequence of all 1s is that adding 1 to it creates a power of two (like 10000). We can check if a number is a power of two using the formula .
Walkthrough: Understanding the Examples
Example 1: n = 5
- Binary of 5 is
101. - Shift by 2:
101 >> 2results in001. - XOR them:
101 ^ 001 = 100. - Apply the power of two check:
100 & 011 = 000. - Result: True.
Example 2: n = 7
- Binary of 7 is
111. - Shift by 2:
111 >> 2results in001. - XOR them:
111 ^ 001 = 110. - Apply the power of two check:
110 & 101 = 100(Not zero). - Result: False.
Code Implementation
C++
class Solution {
public:
bool hasAlternatingBits(int n) {
// Shifting by 2 aligns identical bits in an alternating sequence
const int a = n ^ (n >> 2);
// Check if the result is a power of 2 minus 1 or a related pattern
return (a & (a - 1)) == 0;
}
};
Python
class Solution:
def hasAlternatingBits(self, n: int) -> bool:
# XOR n with itself shifted by 2 to isolate the bit pattern
a = n ^ (n >> 2)
# Using bitwise AND to check for the underlying power-of-two property
return (a & (a - 1)) == 0
JavaScript
/**
* @param {number} n
* @return {boolean}
*/
var hasAlternatingBits = function(n) {
// n ^ (n >> 2) helps identify if the bits were perfectly alternating
const a = n ^ (n >> 2);
// If (a & (a - 1)) is 0, it confirms the bit structure matches our requirement
return (a & (a - 1)) === 0;
};
Key Takeaways
- Bit Shifting: Moving bits to the left or right is a high-speed way to perform multiplication, division, or pattern alignment.
- XOR Logic: The XOR operator is perfect for detecting differences between bit sets.
-
Power of Two Check: The expression
(x & (x - 1)) == 0is a classic programming idiom used to verify if a number has exactly one bit set to 1.
Final Thoughts
This problem is a fantastic introduction to how low-level systems handle data. In real-world software engineering, particularly in embedded systems or network protocols, bit manipulation is used to pack data tightly and save memory. While high-level developers might not use this daily, understanding these patterns is vital for performance-critical applications like cryptography and image processing.
Top comments (0)