Programming problems that involve binary numbers can be challenging but also fun to solve, providing the opportunity to delve deep into the fundamental workings of computers. This article will explore one such problem from Leetcode – the ‘Binary Number with Alternating Bits’ problem. We’ll discuss various approaches using Python and the underlying concepts in detail.
Here’s the problem as given on LeetCode:
Given a positive integer, check whether it has alternating bits: namely, if two adjacent bits will always have different values.
For example, for input
5, the output should be
True. This is because
5 in binary is
101, which has alternating 1s and 0s.
But for input
7, the output should be
False. This is because
7 in binary is
111, which does not have alternating bits.
Understanding the Problem
Before we dive into the solution, it’s important to understand what the problem is asking.
We need to determine whether a given integer, when represented in binary, has alternating 1s and 0s. In other words, no two consecutive bits in the binary representation of the number are the same.
Solution Using Bit Manipulation
Python has a built-in function,
bin(), that can convert an integer into a binary string. We can use this function to get the binary representation of the number and then simply iterate through the string to check for any two consecutive bits that are the same.
Here is a Python function that solves the problem:
def hasAlternatingBits(n): # Convert to binary and remove the "0b" prefix binary = bin(n)[2:] # Iterate through the binary string for i in range(len(binary) - 1): # If two consecutive bits are the same, return False if binary[i] == binary[i+1]: return False # If no two consecutive bits are the same, return True return True
While this solution is straightforward and works, we can also solve the problem using bit manipulation, which is a more optimal and elegant solution.
The optimal solution to this problem involves using bitwise operators.
Here’s the intuition: If a number
n is a binary number with alternating bits, then
n >> 1 is
n with all bits shifted to the right by one place, and
n ^ (n >> 1) should give us a number with all bits set to 1.
Here’s the step-by-step breakdown:
- We first shift the bits of
none place to the right to get
n >> 1.
- We then perform a bitwise XOR operation between
n >> 1.
nhas alternating bits, then all the bits in
n ^ (n >> 1)will be set to 1.
- To check if all the bits in a number are set to 1, we can add 1 to the number and perform a bitwise AND operation between the number and the number + 1. If the result is 0, then all bits in the original number were set to 1.
Here is the Python function implementing the above steps:
def hasAlternatingBits(n): n ^= n >> 1 return n & (n + 1) == 0
This function first calculates
n ^ (n >> 1), and then checks if the result
n & (n + 1) is equal to 0. If it is, the function returns
True, meaning the original number
n has alternating bits. Otherwise, it returns
Testing the Solution
Let’s test the function with some inputs:
print(hasAlternatingBits(5)) # Returns True print(hasAlternatingBits(7)) # Returns False print(hasAlternatingBits(11)) # Returns False print(hasAlternatingBits(10)) # Returns True
The function should return
True for inputs 5 and 10, and
False for inputs 7 and 11. This matches our expectation, verifying the correctness of our function.
Solving the ‘Binary Number with Alternating Bits’ problem on LeetCode not only requires knowledge of Python but also a good understanding of binary numbers and bitwise operations. This problem is a good example of how bitwise operations can lead to efficient and elegant solutions. Understanding how bitwise operators work can be extremely beneficial, especially when dealing with problems related to binary numbers or bit manipulation.