# Bitwise Operations

**Bitwise operations** act on the individual bits of their operands. For example,
a bitwise AND (`&`

) will perform a logical AND (`&&`

) on each pair of bits. ```
14
& 9
```

evaluates to `8`

:

1110 & 1001 -------- 1000

**Logical operators** treat each operand as having only one value.

## Operators

C has a number of operators that work directly on bits.

Operator | Name |
---|---|

`&` |
Bitwise AND |

`│` |
Bitwise OR |

`^` |
Bitwise XOR |

`~` |
Bitwise NOT |

`<<` |
Bit Shift Left |

`>>` |
Bit Shift Right |

The first three operators are explained with truth table below.

`&` |
`│` |
`^` |
||
---|---|---|---|---|

0 | 0 | 0 | 0 | 0 |

0 | 1 | 0 | 1 | 1 |

1 | 0 | 0 | 1 | 1 |

1 | 1 | 1 | 1 | 0 |

The right shift (`>>`

) can be **logical** or **arithmetic**. Logical right shift
pads with zeros, but arithmetic right shift pads with the most significant
bit.

## Examples

Code | Description |
---|---|

`x&(1<<i)` |
Retrieve the ith bit |

`x│=(1<<i)` |
Set the ith bit |

`x&=~(1<<i)` |
Clear the ith bit |

`x^=(1<<i)` |
Flip the ith bit |

Bit-level operations often use masking. A **mask** is a bit pattern that indicates
a selected set of bits within a word. For example, the bit-level operation ```
x &
0xFF
```

yields a value consisting of the least significant byte of x, but with all
other bytes set to 0. The expression `~0`

will yield a mask of all ones,
regardless of the word size of the machine.

### Sum Integers

int add(int x, int y) { if (y == 0) { return x; } else { int carry = (x & y) << 1; return add(x ^ y, carry); } }

### Count 1 Bits

int count(int bits) { int total = 0; while (bits) { total += bits & 1; bits >>= 1; } return total; }

### Erase Lowest Bit

`x&(x - 1)`

equals `x`

with its lowest set bit erased. For example, if ```
x =
00101100
```

, then `x - 1 = 00101011`

, so ```
x&(x - 1) = 00101100 & 00101011 =
00101000
```

.

This fact can be used to reduce the time complexity of counting 1 bits.

int count(int bits) { int total = 0; while (bits) { total += 1; bits &= bits - 1; } return total; }

### Parity

The parity of a binary word is 1 if the number of 1s in the word is odd; otherwise, it is 0. For example, the parity of 1011 is 1, and the parity of 10001000 is 0.

Parity could be computed with brute-force by counting 1 bits (see above) and modding by 2. XOR provides a more efficient solution. Note that the XOR of a group of bits is its parity. For example 1^0^1^1 is 1. Since XOR is associative and commutative, we can process multiple bits at a time.

int parity(int bits) { bits ^= bits >> 32; bits ^= bits >> 16; bits ^= bits >> 8; bits ^= bits >> 4; bits ^= bits >> 2; bits ^= bits >> 1; return bits & 1; /* extract last bit */ }