# 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 */ }