# Bit Manipulation

Bit Manipulation is a technique to manipulate the binary using Bitwise Operation.

Before we get started, I want to introduce ASCII to you. ASCII stands for American Standard Code for Information Interchange. Every character represents a number to ASCII. Such as "a" represent 01100001 in binary or 97 in decimal, "A" represent 01000001 in binary or 65 in decimal, and so on. It is a character encoding standard for electronic communication.

So, every character has a binary number, and the skill to manipulate it is a must for every software engineer. The technique is simple, using bitwise operation.

Here are the bitwise operators:

Symbol | Name | Example |
---|---|---|

~ | NOT |
NOT 0111 (decimal 7) = 1000 (decimal 8) |

& | AND |
0101 (decimal 5) AND 0011 (decimal 3) = 0001 (decimal 1) |

❘ | OR |
0101 (decimal 5) OR 0011 (decimal 3) = 0111 (decimal 7) |

^ | XOR |
0101 (decimal 5) XOR 0011 (decimal 3) = 0110 (decimal 6) |

» | SHIFT RIGHT |
10010111 (decimal −105) SHIFT RIGHT BY 1 = 11001011 (decimal −53) |

« | SHIFT LEFT |
00010111 (decimal +23) SHIFT LEFT BY 1 = 00101110 (decimal +46) |

I hope you can understand my short examples above. If not, let me explain it once again.

- NOT 1 equals to 0.
- 1 AND 1 equals to 1. 1 AND 0 equals to 0.
- 1 OR 1 equals to 1. 1 OR 0 equals to 1.
- 1 XOR 1 equals to 0. 1 XOR 0 equals to 1.
- 0010 (2) SHIFT RIGHT by 1 equals to 0001 (1).
- 0010 (2) SHIFT LEFT by 1 equals to 0100 (4).

```
void print_bits(int number) {
unsigned int check_bit = 1 << (sizeof(int) * 8 - 1);
while (check_bit) {
int result = number & check_bit;
result == check_bit ? printf("1 ") : printf("0 ");
check_bit >>= 1;
}
}
```

Printing Bits. One of the most questions in a programming interview about Bit Manipulation. I use unsigned integer here because I only need a positive number. Integer has a size of 4 bytes. 1 byte is equal to 8 bits. Decrease one for the current position. I use "&" (AND) to check a bit. Print 1 if the result is the same with check_bit. Then, shift right by one for every loop.

```
int count_bits(int number) {
int count = 0;
while (number) {
number &= (number - 1);
count++;
}
return count;
}
```

Counting Bits. Count how many 1s in bits.

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

Reverse Bits. One of the most questions in a programming interview. Shift right the original number and shift left the reversed number. Extract the rightmost bit then add it to the rightmost position of the result.

References:

- https://en.wikipedia.org/wiki/ASCII
- https://en.wikipedia.org/wiki/Bit_manipulation
- https://en.wikipedia.org/wiki/Bitwise_operation