# Bit manipulation cheatsheet

## Get a bit

### Get last bit

`n & 1`

### Check if `n`

is even

`n & 1 == 0`

### Get bit at position `k`

`(n >> k) & 1`

## Set / clear a bit at position `k`

### Set a bit

`n |= 1 << k`

### Clear a bit

`n &= ~(1 << k)`

### Toggle a bit

`^`

is similar to `|`

except that $1 xor 1 = 0$.

`n ^= 1 << n`

## Masking

Write C expressions, in terms of variable `x`

, for the following values.

The least significant byte of `x`

, with all other bits set to $0$.

`x & 0xff`

The least significant byte set to all ones, and all other bytes of `x`

left unchanged.

`x | 0xff`

— *CS-APP practice problem 2.12*

`n & (n - 1)`

trick

`n & n - 1`

has the effect of flipping the least significant $1$ bit of `n`

.

Check out this detailed explanation.

You can use this trick to solve following LeetCode questions.

```
public int hammingWeight(int n) {
int ret = 0;
for (; n != 0; n = n & (n - 1)) ret++；
return ret;
}
```

Notice in the decimal system, we write $10^n$ as $1$ followed by $n$ zeros.

By the same token, the binary representation of $2^n$ is $1$ followed by $n$ zeros.

```
// Check if the number would turn to 0
// after flipping the least significant 1 bit.
public boolean isPowerOfTwo(int n) {
if (n == 0) return false;
long N = (long) n;
return (N & (N - 1)) == 0;
}
```

To check if a number is a power of $4$, we first check if it’s power of $2$ by applying the $n \And (n - 1)$ trick.
A power of $2$ number has only one $1$ bit.
If it’s power of $4$, this $1$ bit must be followed by an even number of $0$ bits.
In other words, the $1$ bit must appear at even position of the binary representation.
We can use a bit mask to check if the 1 bit is at odd position. If so, it’s *not* power of $4$.

```
public boolean isPowerOfFour(int n) {
if (n == 0) return false;
long N = (long) n;
return (N & (N - 1)) == 0
&& (N & 0xaaaaaaaa) == 0;
}
```

Note `0xa`

is equivalent to `0b1010`

.