# Bit Operators

• Leading zeros `0` (i.e., to the left) are meaningless

## `~` NOT

• Invert a bit
• Examples:
• `~0 = 1`
• `~1 = 0`
• `~0111 = 1000`
• `~100 = 011`
• In Java, `~` inverts an `int` and not single bits, so:
``````int b = 0b10;
~b == 11111111111111111111111111111101
``````

## `&` AND

• Results in `1` in each position if the corresponding first bit and second bit are `1`, otherwise `0`.
• Enables to find if a certain bit in a number contains `1` or `0`. Can be considered like multiplying all bits.
• Examples:
• `10 & 11 = 10`
• `0011 & 0010 = 0010`

## `|` OR

• Results in `1` in each position if the corresponding first bit or second bit are `1`, otherwise `0`.
• Enables to set a specific bit to `1`.
• Examples:
• `10 | 11 = 11`
• `0011 | 0010 = 0011`

## `^` XOR

• Exclusive OR – results in `1` in each position if the corresponding first bit or second bit are `1`, but not both, otherwise `0`.
• Enables to compare two bits – `1` means they are different, `0` means they are the same.
• Can be used to invert selected bits in a register. Any bit can be toggled by XOR-ing it with `1`.
• XOR-ing a value against itself yields zero.
• Examples:
• `0101 ^ 0011 = 0110`
• `0010 ^ 1010 = 1000`
• XOR can be used for "backup":
• Calculate `a` and `b`'s XOR: `x = a^b`
• If needed, recover `a`: `a = b^x`
• If needed, recover `b`: `b = a^x`

## `<<` Shift Left

• Add `n` `0` bits to the right.
• A left arithmetic shift by `n` is equivalent to multiplying the number by `2^n`.
• For example: `10111 << 1 = 101110`

## `>>` Shift Right

• Remove `n` bits from the right (`0` or `1`).
• A right arithmetic shift by `n` is equivalent to dividing by `2^n`.
• For example: `10010111 >> 1 = 1001011`

See also Java section on Bit Arithmetics/Operations and Data Structures code examples for BitSet.

## Binary Numbers

``````0 = 0
1 = 1
10 = 2
11 = 3
100 = 4
101 = 5
110 = 6
111 = 7
1000 = 8
1001 = 9
1010 = 10
1011 = 11
1100 = 12
1101 = 13
1110 = 14
1111 = 15
10000 = 16
...
``````
``````10010110
^      ^
|      |------- bit 0
|
|-------------- bit 7
``````

Having a `1` in the `k`-th bit, means that the decimal number is comprised of `2^k`. For example, for the above number:

``````2^7 + 2^4 + 2^2 + 2^1 = 150
``````