---
# System prepended metadata

title: Bit Maniputation
tags: [Data Structures & Algorithms, GeeksforGeeks]

---

### 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)
```

![image](https://hackmd.io/_uploads/rJLkWuoA6.png)



- 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
![image](https://hackmd.io/_uploads/ByiCxrAyR.png)

``` 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
![image](https://hackmd.io/_uploads/SJi7EBRJA.png)

``` 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
![image](https://hackmd.io/_uploads/HyKGIB0kC.png)

``` 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 
![image](https://hackmd.io/_uploads/Bk-PYrRyC.png)
``` 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/

