Bit Manipulation
Bit manipulation is the act of algorithmically manipulating bits or binary digits. It is a fast and efficient way to perform operations such as addition, subtraction, multiplication, and division on binary numbers. Bit manipulation is commonly used in computer science and programming to optimize algorithms and data structures.
Bitwise Operators
Bitwise operators are used to perform operations on individual bits of binary numbers. The following are the bitwise operators available in most programming languages:
-
AND (
&): The AND operator performs a bitwise AND operation on two binary numbers. It returns 1 if both bits are 1; otherwise, it returns 0.0 & 0 = 0 0 & 1 = 0 1 & 0 = 0 1 & 1 = 1 5 & 3 = 1 # 101 & 011 = 001 -
OR (
|): The OR operator performs a bitwise OR operation on two binary numbers. It returns 1 if at least one of the bits is 1; otherwise, it returns 0.0 | 0 = 0 0 | 1 = 1 1 | 0 = 1 1 | 1 = 1 5 | 3 = 7 # 101 | 011 = 111 -
XOR (
^): The XOR operator performs a bitwise XOR (exclusive OR) operation on two binary numbers. It returns 1 if the bits are different; otherwise, it returns 0.0 ^ 0 = 0 0 ^ 1 = 1 1 ^ 0 = 1 1 ^ 1 = 0 5 ^ 3 = 6 # 101 ^ 011 = 110 -
NOT (
~): The NOT operator performs a bitwise NOT operation on a binary number. It flips the bits, changing 1s to 0s and 0s to 1s.~0 = 1 ~1 = 0 ~5 = -6 # ~0101 = 1010 -
Left Shift (
<<): The left shift operator shifts the bits of a binary number to the left by a specified number of positions. It appends zeros to the right.5 << 1 = 10 # 101 << 1 = 1010 5 << 2 = 20 # 101 << 2 = 10100 -
Right Shift (
>>): The right shift operator shifts the bits of a binary number to the right by a specified number of positions. It appends zeros to the left.5 >> 1 = 2 # 101 >> 1 = 10 5 >> 2 = 1 # 101 >> 2 = 1
Common Bit Manipulation Techniques
1. Check if a Number is Even or Odd
To check if a number is even or odd, you can use the bitwise AND operator. An even number has its least significant bit (LSB) set to 0, while an odd number has its LSB set to 1.
def is_even(n):
return n & 1 == 0
def is_odd(n):
return n & 1 == 1
2. Swap Two Numbers
To swap two numbers without using a temporary variable, you can use the XOR operator. The XOR operator has the property that a ^ b ^ b = a, which allows you to swap two numbers without using additional memory.
def swap(a, b):
a = a ^ b
b = a ^ b
a = a ^ b
return a, b
3. Set a Bit
To set a specific bit in a binary number, you can use the OR operator. To set the i-th bit of a number n, you can use the expression n | (1 << i).
def set_bit(n, i):
return n | (1 << i)
4. Clear a Bit
To clear a specific bit in a binary number, you can use the AND operator. To clear the i-th bit of a number n, you can use the expression n & ~(1 << i).
def clear_bit(n, i):
return n & ~(1 << i)
5. Toggle a Bit
To toggle a specific bit in a binary number, you can use the XOR operator. To toggle the i-th bit of a number n, you can use the expression n ^ (1 << i).
def toggle_bit(n, i):
return n ^ (1 << i)
6. Check if a Bit is Set
To check if a specific bit in a binary number is set, you can use the AND operator. To check if the i-th bit of a number n is set, you can use the expression (n & (1 << i)) != 0.
def is_bit_set(n, i):
return (n & (1 << i)) != 0
Problems
-
Question 1. Number of 1 Bits
Easy
Given an integer n, return the number of 1 bits in its binary representation.
Example 1:
Input: n = 00000000000000000000000000001011
Output: 3
Example 2:
Input: n = 00000000000000000000000010000000
Output: 1
def hamming_weight(n):
pass
assert hamming_weight(11) == 3, "Test case 1 failed"
assert hamming_weight(128) == 1, "Test case 2 failed"
assert hamming_weight(4294967293) == 31, "Test case 3 failed"
-
Question 2. Counting Bits
Easy
Given a non-negative integer n, for every number i in the range 0 ≤ i ≤ n, calculate the number of 1 bits in its binary representation and return them as an array.
Example 1:
Input: n = 2
Output: [0,1,1]
Example 2:
Input: n = 5
Output: [0,1,1,2,1,2]
def count_bits(n):
pass
assert count_bits(2) == [0,1,1], "Test case 1 failed"
assert count_bits(5) == [0,1,1,2,1,2], "Test case 2 failed"
assert count_bits(0) == [0], "Test case 3 failed"
-
Question 3. Reverse Bits
Easy
Reverse the bits of a given 32-bit unsigned integer.
Example 1:
Input: x = 123
Output: 321
Example 2:
Input: x = -123
Output: -321
Example 3:
Input: x = 120
Output: 21
def reverse_bits(x):
pass
assert reverse_bits(123) == 321, "Test case 1 failed"
assert reverse_bits(-123) == -321, "Test case 2 failed"
assert reverse_bits(120) == 21, "Test case 3 failed"
-
Question 4. Missing Number
Easy
Given an array nums containing n distinct numbers in the range [0, n], return the only number in the range that is missing from the array.
Example 1:
Input: nums = [3,0,1]
Output: 2
Example 2:
Input: nums = [0,1]
Output: 2
Example 3:
Input: nums = [9,6,4,2,3,5,7,0,1]
Output: 8
def missing_number(nums):
pass
assert missing_number([3,0,1]) == 2, "Test case 1 failed"
assert missing_number([0,1]) == 2, "Test case 2 failed"
assert missing_number([9,6,4,2,3,5,7,0,1]) == 8, "Test case 3 failed"
-
Question 5. Sum of Two Integers
Medium
Given two integers a and b, return the sum of the two integers without using the operators + and -.
Example 1:
Input: a = 1, b = 2
Output: 3
Example 2:
Input: a = -2, b = 3
Output: 1
def get_sum(a, b):
pass
assert get_sum(1, 2) == 3, "Test case 1 failed"
assert get_sum(-2, 3) == 1, "Test case 2 failed"
assert get_sum(-1, 1) == 0, "Test case 3 failed"