- Published on
Bit Manipulation
- Authors
- Name
- Richard Feng
- @richard____feng
Computers store information using bits. A bit (short for "binary digit") stores either the value or . When we have only two choices, we can use a bit.
The following examples in our daily lives can be represented using bits:
Is a lightbulb on or off?
Is a button enabled or disabled?
Is the current time AM or PM?
There are different bitwise operations used in bit manipulation. These bit operations operate on the individual bits of bit patterns. Bit operations are fast and can be used in optimizing time complexity. Some common bit operators are:
| Symbol | Operator | Description |
|---|---|---|
| ~ | Not | Bit n of ~x is the opposite of bit n of x |
| & | And | Bit n of x & y is 1 if bit n of x and bit n of y is 1. |
| | | Or | Bit n of x | y is 1 if bit n of x or bit n of y is 1. |
| ^ | Exclusive Or | Bit n of x ^ y is 1 if bit n of x or bit n of y is 1 but not if both are 1. |
| >> | Right Shift (divide by 2) | Bit n of x >> s is bit n - s of x. |
| << | Left Shift (multiply by 2) | Bit n of x << s is bit n + s of x. |
Computers store information using bits. A bit (short for "binary digit") stores either the value or . When we have only two choices, we can use a bit.
The following examples in our daily lives can be represented using bits:
Is a lightbulb on or off?
Is a button enabled or disabled?
Is the current time AM or PM?
There are different bitwise operations used in bit manipulation. These bit operations operate on the individual bits of bit patterns. Bit operations are fast and can be used in optimizing time complexity.
| And (&): | 0 & 0 = 0 | 1 & 0 = 0 | 0 & 1 = 0 | 1 & 1 = 1 |
| Or (|): | 0 | 0 = 0 | 1 | 0 = 1 | 0 | 1 = 1 | 1 | 1 = 1 |
| Xor (^): | 0 ^ 0 = 0 | 1 ^ 0 = 1 | 0 ^ 1 = 1 | 1 ^ 1 = 0 |
From the truth table above, we can see:
myBits ^ 0 : No change
myBits ^ 1 : Flip
Some examples:
N = 5 = (101)2
~N = ~5 = ~(101)2 = (010)2 = 2
A = 5 = (101)2
B = 3 = (011)2
A & B = (101)2 & (011)2= (001)2 = 1
A | B = (101)2 | (011)2 = (111)2 = 7
A ^ B = (101)2 ^ (011)2 = (110)2 = 6
Left Shift:
x << y means x shifted y bits to the left. If you start shifting and run out of space, the bits just “drop off”. For example:
00011001 << 2 = 01100100
00011001 << 4 = 10010000
Left shifting is the equivalent of multiplying by a power of two:
x << n = x * (1 << n)
More specifically:
8 << 2 = 8 * (1 << 2) = 32
Right Shift:
x >> y means x shifted y bits to the right. If you start shifting and run out of space, the bits just “drop off” at the end. A bitwise right-shift will be the equivalent of integer division by 2. Example:
00011001 >> 2 = 00000110
00011001 >> 4 = 00000001