### Bit Maniputation
- Bit manipulation or Bitwise operator
- It operates on binary representation of a number
- Its a technique
- Operators or Gates in elecronics
- AND -> &
- OR -> |
- XOR -> a'b + ba' -> different will output 1 -> ^
- NOT or negation operator - ! -> ~
- ">>" - Right shift
- "<<" - left shift
- operates on base 2 of a number
- each digit is less than base (0,1 for base 2)
- each digit in binary rep is called bit
- 1 -> set bit and 0 -> unset bit
- full adder and half adder -> addtion, multiplication etc..
- power of base - only last digit will have set bit
- 10 ** 2 -> 100
- 10 ** 5 -> 10000
- 2 ** 3 -> 1000 - 2 ** 3
- Other operators
- Left sift -> << -> makes number bigger -> * 2
- Right sift -> >> -> makes number smaller -> / 2
- typically 32 bits are used to store integer
- Smallest & biggest bitwise numbers
``` python
print(bin(0)) -> 0b0
print(bin((2 ** 32) - 1)) -> 0b11111111111111111111111111111111
```
- power of 2 numbers
- 1 = 1
- 2 = 10
- 4 = 100
- 8 = 1000
- 2 ^ n - 1 numbers
- 1 - 1 = 0
- 2 - 1 = 1
- 4 - 1 = 11
- 8 - 1 = 111
- n & (n - 1) = 0 where n is power of 2
- n & (n - 1) -> would remove last set bit
- reverse bits
- k bit nust be swapped with 31 - k bit
- negative numbers are stored in 2's complement of x
- range of numbers [-2 ** (n - 1) to 2 ** (n - 1) - 1]
- steps to get twos compliment of a number
- invert all bits
- add 1
- Direct formula: 2 ^ 32 - x
- not, left shift, right shift operations for negative number are not defined in standard
- alternatives to 2s complement form
- signed bit
- first bit of 32 bits will be used to represented
- disadvantage: 0 will have 2 representations
- 1s complement form
- Properties of xor
- x ^ x = 0 -> xor of same number returns 0
- 0 ^ x = x -> xor of 0 and any number returns that number
- x ^ y = y ^ x -> xor order doesnt matter
Python
- decimal to binary
``` python
a = 10
print(bin(n))
```
- binary to decimal
``` python
a = '100'
print(int(a, 2))
a = 0b100
print(a)
```
- 32bit binary representation
``` python
def binary_rep(n):
return bin(n)[2:].zfill(32)
```
- check if last bit is set or not
``` python
x & 1 == 1
or
x % 2 == 1
```
- unset last set bit
```
n & (n - 1)
```
- check if ith bit of x is set or not
``` python
x & (1 << i) != 0 # true if ith bit is set
or
(x >> i) & 1 == 1 # true if ith bit is set
```
- The & operator can be used to quickly check if a number is odd or even
``` python
(x & 1)
```
- create a bit mask
``` python
(1 << k)
```
- turn on a bit in a number
``` python
n | (1 << k)
```
- get last set bit ?
``` python
x & (~(x - 1))
```
### Concepts
- is power of 2
- check last bit if n == 0 return False
- if last bit is not 1
- check last is zero
- right shift
- if last bit is 1 then return false
- find odd occuring number
- bitwise XOR of all number will rust in odd occuring number
- find two odd occuring numbers
- xor of 2 odd occuring numbers = find xor of all numbers
- find first set bit for above number (Note: it helps to find that kth bit that is different in two numbers)
- based on that seperate into two groups
- run xor on them each to find the off occuring in each group
- The left-shift and right-shift operators are equivalent to multiplication and division by 2 respectively
- The & operator can be used to quickly check if a number is odd or even
``` python
(x & 1)
```
- create a bit mask
``` python
(1 << k)
```
- turn on a bit in a number
``` python
n | (1 << k)
```
### Problems
- check kth bit is set or not
``` python
# TC: O(1)
# SC: O(1)
def is_kthbit_set(num, k):
if num & 1 << (k - 1) != 0:
return True
return False
```
``` python
# TC: O(1)
# SC: O(1)
def is_kthbit_set(num, k):
return ((num >> (k - 1)) & 1 ) != 0
```
-count number of set bits
``` python
#TC: O(log n)
#SC: O(1)
def count_set_bits(num):
result = 0
while num > 0:
if num & 1 != 0:
result += 1
num = num >> 1
return result
```
``` python
#TC: O(log n)
#SC: O(1)
def count_set_bits(num):
result = 0
while num > 0:
if num & 1 != 0:
result += 1
num = num >> 1
return result
```
``` python
#TC: O(log n)
#SC: O(1)
def num_set_bits(n):
total = 0
while n > 0:
n = n & (n - 1) # would remove last set bit
total += 1
return total
```
- power of 2
``` python
# TC: O(1)
# SC: O(1)
def is_power_o_2(num):
if num & (num - 1) == 0:
return True
return False
```
- one odd ocurring
``` python
def find_one_odd_occuring(nums):
result = 0
for x in nums:
result = result ^ x
return result
```
- find two odd occuring
``` python
# TC: O(n)
# SC: O(1)
def find_two_odd_occuring(nums):
# xor of 2 odd occuring numbers
two_odd = 0
for x in nums:
two_odd = two_odd ^ x
# find position of first set bit
first_set_bit = 0
while two_odd > 0:
if two_odd & 1 == 1:
break
first_set_bit += 1
two_odd = two_odd >> 1
# split into two sets
first_odd = 0
second_odd = 0
for x in nums:
if x & (1 << first_set_bit) != 0:
first_odd = first_odd ^ x
else:
second_odd = second_odd ^ x
return (first_odd, second_odd)
```
- powerset
- find missing number
``` python
def missing_number(array,n):
result = 0
for item in range(1, n+1, 1):
result ^= item
for item in array:
result ^= item
return result
```
- reverse bits
k bit must be swapped with 31 - k bit
### Tricks
- https://www.geeksforgeeks.org/bitwise-operators-in-c-cpp/
- https://www.geeksforgeeks.org/bits-manipulation-important-tactics/
- https://www.geeksforgeeks.org/bitwise-hacks-for-competitive-programming/
- https://www.geeksforgeeks.org/bit-tricks-competitive-programming/
- https://www.geeksforgeeks.org/category/bit-magic/
Sign in with Wallet
Connect another wallet