We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Binary Number with Alternating Bits

Difficulty: Easy

Problem Description

Given a positive integer, check whether it has alternating bits: namely, if two adjacent bits will always have different values.

Key Insights

  • The binary representation of a number can be checked for alternating bits by iterating through its bits.
  • Adjacent bits are considered alternating if one is 0 and the other is 1.
  • A simple way to identify this pattern is to use bit manipulation techniques.

Space and Time Complexity

Time Complexity: O(log n) - We iterate through the number of bits in the binary representation. Space Complexity: O(1) - We use a constant amount of space.

Solution

To determine if a number has alternating bits, we can use a bit manipulation approach. The idea is to repeatedly shift the bits of the number to the right and check the last two bits. If they are the same, then the number does not have alternating bits. We can also use a mask to create an alternating pattern to compare against.

  1. Initialize a variable prev_bit to the last bit of the number.
  2. Right shift the number and check the last bit at each step.
  3. If the last bit is the same as prev_bit, return false.
  4. If we traverse all bits without finding two adjacent bits that are the same, return true.

Code Solutions

def hasAlternatingBits(n):
    prev_bit = n & 1  # Get the last bit
    n >>= 1           # Right shift the number
    while n > 0:
        current_bit = n & 1  # Get the last bit
        if current_bit == prev_bit:
            return False
        prev_bit = current_bit
        n >>= 1  # Right shift the number again
    return True
← Back to All Questions