BIT MANIPULATION
1. Checking if a Number is Odd or Even
Odd: A number is odd if its least significant bit (LSB) is 1.
python
Copy code
if (n & 1) == 1:
# n is odd
Even: A number is even if its least significant bit (LSB) is 0.
python
Copy code
if (n & 1) == 0:
# n is even
2. Swapping Two Numbers Without a Temporary Variable
Using XOR:
python
Copy code
a=a^b
b=a^b
a=a^b
3. Checking if a Number is a Power of Two
A number NNN is a power of two if it has only one bit set (i.e., only one
1 in its binary representation).
python
Copy code
def is_power_of_two(n):
return (n > 0) and (n & (n - 1)) == 0
This works because powers of two have only one bit set, and
subtracting 1 from such a number flips all the lower bits.
4. Counting Set Bits (Hamming Weight)
Use the n & (n - 1) trick to clear the lowest set bit in each iteration.
python
Copy code
def count_set_bits(n):
count = 0
while n:
n &= (n - 1) # Clears the lowest set bit
count += 1
return count
5. Flipping All Bits
Use the bitwise NOT operator ~.
python
Copy code
flipped = ~n
6. Getting the Lowest Set Bit
The lowest set bit of a number can be extracted with:
python
Copy code
lowest_set_bit = n & -n
This trick works because -n is the two's complement, which flips all bits
up to the lowest set bit.
7. Clearing the Lowest Set Bit
To clear the lowest set bit, use:
python
Copy code
n = n & (n - 1)
8. Setting the kkk-th Bit
To set the kkk-th bit (0-based index from the right), use:
python
Copy code
n = n | (1 << k)
9. Clearing the kkk-th Bit
To clear the kkk-th bit, use:
python
Copy code
n = n & ~(1 << k)
10. Toggling the kkk-th Bit
To toggle the kkk-th bit, use:
python
Copy code
n = n ^ (1 << k)
11. Checking if the kkk-th Bit is Set
To check if the kkk-th bit is set, use:
python
Copy code
is_set = (n & (1 << k)) != 0
12. Isolating the Rightmost 1-bit
To get a mask for just the rightmost 1-bit:
python
Copy code
rightmost_one = n & -n
13. Rounding Up to the Next Power of Two
Given a number n, the following trick rounds it up to the next power of
two:
python
Copy code
n -= 1
n |= n >> 1
n |= n >> 2
n |= n >> 4
n |= n >> 8
n |= n >> 16
n += 1
This works by propagating the highest set bit to all lower positions,
then adding 1.
14. Finding the Position of the Most Significant Bit (MSB)
You can use the following loop:
python
Copy code
def msb_position(n):
pos = -1
while n:
pos += 1
n >>= 1
return pos
15. Reversing the Bits of an Integer
Use a loop to reverse the bits by shifting.
python
Copy code
def reverse_bits(n, bit_size=32):
result = 0
for _ in range(bit_size):
result = (result << 1) | (n & 1)
n >>= 1
return result
16. Binary Representation of Subsets
Using bit manipulation to generate all subsets of a set:
python
Copy code
def generate_subsets(arr):
n = len(arr)
subsets = []
for i in range(1 << n): # Loop from 0 to 2^n - 1
subset = []
for j in range(n):
if i & (1 << j): # Check if j-th bit is set
subset.append(arr[j])
subsets.append(subset)
return subsets
17. Swapping Even and Odd Bits
This swaps even and odd bits in a 32-bit number.
python
Copy code
def swap_even_odd_bits(n):
even_bits = n & 0xAAAAAAAA # Mask for even bits
odd_bits = n & 0x55555555 # Mask for odd bits
even_bits >>= 1 # Shift even bits to the right
odd_bits <<= 1 # Shift odd bits to the left
return even_bits | odd_bits
18. Modulo Power of Two
If you want to compute nmod 2mn \mod 2^mnmod2m, use:
python
Copy code
result = n & ((1 << m) - 1)
This is equivalent to nmod 2mn \mod 2^mnmod2m and is faster than
the modulus operator.
19. Checking if Two Numbers Have Opposite Signs
You can check if two numbers xxx and yyy have opposite signs by:
python
Copy code
def opposite_signs(x, y):
return (x ^ y) < 0
This works because the XOR of a positive and a negative number will
have the sign bit set.
20. Counting Leading Zeros (for 32-bit integers)
Counting leading zeros can be done with:
python
Copy code
def count_leading_zeros(n):
count = 0
while (n & (1 << 31)) == 0 and n != 0:
count += 1
n <<= 1
return count
These bit manipulation techniques can greatly optimize code performance in
scenarios where speed is crucial, particularly in low-level programming,
competitive programming, and when dealing with binary data directly.
4o
