Pular para o conteúdo principal

Binary Number with Alternating Bits

Given a positive integer N, return whether or not it has alternating bit values.

Example(s)​

Example 1:

Input: N = 5
Output: true
Explanation:
5 in binary is 101 which alternates bit values between 0 and 1.
Bits: 1, 0, 1 (alternating)

Example 2:

Input: N = 8
Output: false
Explanation:
8 in binary is 1000 which does not alternate bit values between 0 and 1.
Bits: 1, 0, 0, 0 (has consecutive 0s)

Example 3:

Input: N = 7
Output: false
Explanation:
7 in binary is 111 which does not alternate bit values.
Bits: 1, 1, 1 (has consecutive 1s)

Example 4:

Input: N = 10
Output: true
Explanation:
10 in binary is 1010 which alternates bit values.
Bits: 1, 0, 1, 0 (alternating)

Solution​

The solution uses bit manipulation:

  1. Extract bits: Get each bit using bitwise operations
  2. Check adjacent bits: Compare each bit with the previous one
  3. Verify alternation: Ensure no two adjacent bits are the same
  4. Return result: Return true if all adjacent bits differ

JavaScript Solution - Bit Manipulation

/**
* Check if number has alternating bits
* @param {number} N - Positive integer
* @return {boolean} - True if bits alternate
*/
function hasAlternatingBits(N) {
let prevBit = N & 1; // Get last bit
N = N >> 1; // Shift right to remove last bit

while (N > 0) {
  const currentBit = N & 1; // Get current last bit
  
  // If current bit equals previous bit, not alternating
  if (currentBit === prevBit) {
    return false;
  }
  
  prevBit = currentBit;
  N = N >> 1; // Shift right to get next bit
}

return true;
}

// Test cases
console.log('Example 1:', hasAlternatingBits(5)); 
// true (101)

console.log('Example 2:', hasAlternatingBits(8)); 
// false (1000)

console.log('Example 3:', hasAlternatingBits(7)); 
// false (111)

console.log('Example 4:', hasAlternatingBits(10)); 
// true (1010)

console.log('Test 5:', hasAlternatingBits(1)); 
// true (1)
Output:
Click "Run Code" to execute the code and see the results.

Alternative Solution (XOR Pattern)​

Here's an alternative approach using XOR:

/**
 * Alternative: Check using XOR pattern
 */
function hasAlternatingBitsXOR(N) {
  // Shift right and XOR with original
  // For alternating bits, this creates a pattern of all 1s
  const shifted = N >> 1;
  const xor = N ^ shifted;
  
  // Check if xor + 1 is a power of 2
  // (all 1s + 1 = power of 2)
  return (xor & (xor + 1)) === 0;
}

Alternative Solution (String-based)​

Here's a string-based approach for clarity:

/**
 * String-based approach (for clarity)
 */
function hasAlternatingBitsString(N) {
  const binary = N.toString(2);
  
  for (let i = 1; i < binary.length; i++) {
    if (binary[i] === binary[i - 1]) {
      return false;
    }
  }
  
  return true;
}

Complexity​

  • Time Complexity: O(log N) - Where log is base 2. We process each bit once.
  • Space Complexity: O(1) - Only using a constant amount of extra space.

Approach​

The solution uses bit manipulation:

  1. Get last bit:

    • Use N & 1 to get the least significant bit
    • Store it as the previous bit

  2. Shift right:

    • Use N >> 1 to remove the last bit
    • This moves to the next bit

  3. Check adjacent bits:

    • Compare current bit with previous bit
    • If they're equal, bits don't alternate → return false

  4. Continue:

    • Update previous bit
    • Repeat until N becomes 0

  5. Return true:

    • If all adjacent bits differ, return true

Key Insights​

  • Bit extraction: Use & 1 to get last bit
  • Right shift: Use >> 1 to move to next bit
  • Compare adjacent: Check if current bit equals previous bit
  • Early return: Return false as soon as we find two equal adjacent bits
  • O(log N) time: Process each bit once

Step-by-Step Example​

Let's trace through Example 1: N = 5

N = 5 (binary: 101)

Step 1:
  prevBit = 5 & 1 = 1 (last bit)
  N = 5 >> 1 = 2 (binary: 10)

Step 2:
  currentBit = 2 & 1 = 0
  currentBit (0) === prevBit (1)? No ✓
  prevBit = 0
  N = 2 >> 1 = 1 (binary: 1)

Step 3:
  currentBit = 1 & 1 = 1
  currentBit (1) === prevBit (0)? No ✓
  prevBit = 1
  N = 1 >> 1 = 0

N = 0, exit loop
Result: true (all adjacent bits differ)

Visual Representation​

Example 1: N = 5

Binary:  1  0  1
         ↑  ↑  ↑
        bit2 bit1 bit0

Check adjacent:
  bit1 (0) vs bit0 (1): Different ✓
  bit2 (1) vs bit1 (0): Different ✓
  
Result: true

Example 2: N = 8

Binary:  1  0  0  0
         ↑  ↑  ↑  ↑
        bit3 bit2 bit1 bit0

Check adjacent:
  bit1 (0) vs bit0 (0): Same ✗
  
Result: false

Example 3: N = 10

Binary:  1  0  1  0
         ↑  ↑  ↑  ↑
        bit3 bit2 bit1 bit0

Check adjacent:
  bit1 (1) vs bit0 (0): Different ✓
  bit2 (0) vs bit1 (1): Different ✓
  bit3 (1) vs bit2 (0): Different ✓
  
Result: true

Edge Cases​

  • N = 1: Returns true (single bit)
  • N = 2: Returns true (10 in binary)
  • N = 3: Returns false (11 in binary, consecutive 1s)
  • Powers of 2: Returns false (e.g., 8 = 1000, consecutive 0s)
  • All 1s: Returns false (e.g., 7 = 111)

Important Notes​

  • Positive integer: Problem states N is positive
  • Alternating means: No two adjacent bits are the same
  • Bit manipulation: Efficient way to check bits
  • Early termination: Return false as soon as we find equal adjacent bits
  • O(log N) time: Based on number of bits

Why XOR Approach Works​

Key insight:

  • For alternating bits like 1010, if we shift right and XOR:
    • 1010 ^ 0101 = 1111 (all 1s)
  • All 1s + 1 = power of 2
  • Check: (1111 & 10000) === 0 → true

Example:

N = 10 (1010)
Shifted = 5 (0101)
XOR = 10 ^ 5 = 15 (1111)
15 + 1 = 16 (10000)
15 & 16 = 0 → true
  • Number of 1 Bits: Count set bits
  • Reverse Bits: Different bit manipulation
  • Power of Two: Check if number is power of 2
  • Single Number: Different bit manipulation

Takeaways​

  • Bit manipulation efficiently checks bits
  • Compare adjacent bits to verify alternation
  • Early return when finding equal adjacent bits
  • O(log N) time based on number of bits
  • O(1) space for the algorithm