# A.6: Bit Manipulation

- 1.Understand that computers store values in code as sequences of bits (data type with value 0 or 1). Computers represent numbers with bits in binary format.
- 2.Bit manipulation refers to manipulation of the bits that form a value using bitwise operators
- 3.Know the 6 most common bitwise operators (
`&`

,`|`

,`~`

,`^`

,`<<`

, and`>>`

) and what they do

Computers store all data as sequences of 0s and 1s in a data type called a "bit". Programming languages like JavaScript automatically translate JavaScript to bits for us, thus we rarely need to think of bits while building apps. However, there are several algorithm problems occasionally tested in interviews that can be solved more efficiently by manipulating bits with bitwise operators instead of usual JavaScript commands, thus we learn bit manipulation.

Bit manipulation refers to changing bits in a value using bitwise operators. In the algorithm interview context, this typically involves manipulating bits that represent numbers.

There are 6 most common bitwise operators:

`&`

, `|`

, `~`

, `^`

, `<<`

, and `>>`

. Let us examine them in a table.Operator | Name | Example | Description |
---|---|---|---|

`&` | Bitwise And | `a & b` | Compare bits of values `a` and `b` and produce a result based on the comparison. In the result, bits in each position that were both 1 in `a` and `b` stay 1, otherwise become 0. |

`|` | Bitwise Or | `a | b` | Compare bits of values `a` and `b` and produce a result based on the comparison. In each bit of the result, if either `a` or `b` had a 1 bit in that position, that bit is now 1. |

`~` | Bitwise Not | `~a` | Produce a result where all bits in `a` are reversed. If any bit in `a` was 0, the same bit in the result is 1 and vice versa. |

`^` | Bitwise Xor (pronounced "x-or" or "exclusive or") | `a ^ b` | Same as Bitwise Or, except if the same bit in both values is 1, that bit is 0 in the result. |

`<<` | Bitwise Left Shift | `a << 1` | Shift all bits in `a` to the left by the number to the right of the operator, inserting a 0 bit to the right of the original number for every shift. |

`>>` | Bitwise Right Shift | `a >> 1` | Shift all bits in `a` to the right by the number to the right of the operator, deleting the right-most bit of the original number with every shift. |

Before trying bitwise operators on your own in a Node console, read the following article with diagrams on how each operator works, and watch the following illustrative videos.

Understanding Bitwise Operators

Code Envato Tuts+

Understanding Bitwise Operators

Introduction to basic bitwise operators and how they can be used in practice

Deeper introduction to binary numbers and how to manipulate those numbers using bitwise operators

Example of how to add 2 numbers using only bitwise operators

- 1.
- 1.Hint: If
`A XOR B == C`

, then`C XOR A == B`

and`C XOR B == A`

. - 2.
- 3.

Hint: For JavaScript, consider using the built-in

`toString(2)`

method on numbers to convert integers (aka decimal numbers) to binary numbers, and `toString(10)`

to convert binary numbers to integers. For Python, consider using the equivalent built-in functions `bin`

and `int`

.- 1.
- 2.
- 3.
- 1.Hint: We cannot just use the
`~`

operator because JavaScript and Python integers are signed by default, and the problem assumes unsigned integers. Solution here.

- 4.

- 1.
- 2.
- 3.
- 1.Hint: Unsigned integer means the number is always positive and has no signed bit

- 4.
- 1.Hint: Requires trick to understand what happens when we XOR a number with 0, and when we XOR a number with itself

Last modified 1yr ago