# Bit manipulation

* char :
  * 1 bytes, 8 bits
  * ASCII: 0< char <127
* int:&#x20;
  * 4bytes, 32bits
* double, float:&#x20;
  * 8bytes, 32bits

## 1.Flip operation

```
char x = 'A' // 01000001
char y = ~x; // 10111110
```

## 2.And operation

```
char x = 'A';  // 01000001
char y = 'L';  // 01001100
char z = x & y;// 01000000
```

## 3.Or operation

```
char x = 'A';  // 01000001
char y = 'L';  // 01001100
char z = x | y;// 01001101
```

## 4.XOR operation

* 兩個同時等於0, 兩個不同時等於1
* b ^ 11111111 = \~b&#x20;
* b ^ b = 0

```
char x = 'A';  // 01000001
char y = 'L';  // 01001100
char z = x ^ y;// 00001101
```

## 5.Shift operation

```
char x = 'A';  // 01000001
char z = x >> 3;// 00001000 shift each bit 3 places to the right
char y = x << 3;// 00001000 shift each bit 3 places to the left
```

## 6.Get the Nth bit

* 用Nth為1的check bit做and運算, 再shift left

```
(b & 00010000) << 4
```

```
int get_nth_bit(int num, int n)
{
    int check_bit = 1 << n;
    int and_bit = num & check_bit;
    return and_bit == check_bit;
}
```

## 7.Set the Nth bit to 1

```
int set_nth_bit_to_1(int num, int n)
{
    int set_bit = 1 << n;
    return num | set_bit;
}
```

## 8.Print bits an integer

* Shift it left sizeof(int)\*8 - 1 times

```
void print_bits(int num)
{
    unsigned int check_bit = 1 << (sizeof(int) * 8 - 1);
    while(check_bit != 0)
    {
        int result = num & check_bit;
        if (result == check_bit)
        {
            printf("%d\n", 1);
        }
        else
        {
            printf("%d\n", 0);
        }
        check_bit = check_bit >> 1; 
    }
    printf("\n");
}
```

## 9.Count the number of 1 bits

* The simple way is very similar to the print bits example: O(N)
* binary subtraction: n & (n - 1): O(1)

```
int count_ls_optimized(int num)
{
    int count = 0;
    while(num != 0)
    {
        num = num & (num - 1);
        count++;
    }
    return count++;
}
```

## 10.Reverse the bits in an integer

```
int reverse_bits(int num)
{
    int reverse_num = 0;
    unsigned int count = sizeof(int)*8 -1;
    while(num != 0)
    {
        int last_bit = num & 1;
        reverse_num = reverse_num | last_bit;
        reverse_num = reverse_num << 1;
        num = num >> 1;
        count--;
    }
    
    reverse_num = reverse_num << count;
    return reverse_num;
}
```
