# Bits Manipulation

Bits Manipulation is a topic rarely seen in programming interviews, but superuseful for any programmer. The most seen usecase of bit manipulation is probably masks when you are optimizing a storage for a pre-known set of flags.

Basic bit operations are `& (AND), | (OR), ^ (XOR), ~ (NOT), left and right shifts <<, >>, <<<, >>> (two last ones are meant for unsigned numbers)`

Here’s how they all work:

### AND

```
AND - only keeps matching bits from two numbers
00011100
AND
00001110
=
00001100
```

### OR

```
OR - sets bit '1' if there's '1' at the same position in both numbers
00011100
OR
00001110
=
00011110
```

### XOR

```
XOR - sets bit '1' if bits are different in two numbers
00011100
XOR
00001110
=
00010010
```

In an attempt of making XOR even clearer, here’s the table:

A | B | ^ (XOR) |

0 | 0 | 0 |

0 | 1 | 1 |

1 | 0 | 1 |

1 | 1 | 0 |

## Basic tricks

### A ^ A = 0

If you’ll do XOR operation on a number itself, the result is 0.

This is cool as it allows us to solve problems like finding a non-repeating number in a sequence where each number repeats even number of times in a really nice way.

E. g. imagine you have an array of [3, 3, 2, 2, 1, 5, 3, 5, 3] and you need to find that single number. All you have to do is basically XOR everything through `for (int i = 0; i < nums.length; i++) { result ^= nums[i]; }`

.

You can try it yourself here:

Simple illustration to how it works:

```
result = 0
^ 3 result = 000 ^ 011 = 011
^ 3 result = 011 ^ 011 = 000
^ 2 result = 000 ^ 010 = 010
^ 2 result = 010 ^ 010 = 000
^ 1 result = 000 ^ 001 = 001
^ 5 result = 001 ^ 101 = 100
^ 3 result = 100 ^ 011 = 111
^ 5 result = 111 ^ 101 = 010
^ 3 result = 010 ^ 011 = 001
```

### A & 1 to check if number is odd or even (alternative to A % 2)

A & 1 basically gets last bit of a number and we know that if it’s 1 then number is odd, if it’s 0 it’s even, e. g.:

```
2 & 1 = 10 & 1 = 0 (even)
3 & 1 = 11 & 1 = 1 (odd)
101 & 1 = 1100101 & 1 = 1 (odd)
```

### A » 1 to divide number by two (alternative to Math.floor(A / 2))

Right shift operator is handy in removing one last bit from a number

```
2 >> 1 = 10 >> 1 = 1
101 >> 1 = 1100101 >> 1 = 110010 = 50 =)
```

Make your fellow colleagues excited (please no) writing:

Similar to this, `A << 1`

can be used to multiply number by 2.

### Bitmasks operations

To set a bit at a position:

To remove a bit at a position:

To check the flag in a bitmask:

To make it even more clear (or more confusing):

Why would you use bitmasks during your day-to-day coding? Simple answer - bitmask is just 1 integer (so just 8 to 64 bits [usually]).

### Counting ‘1’s in a number

The trick here is to use `>>`

and `&`

operators - we’ll just be checking last bit of a number and removing it, see e. g.:

```
result = 0
a = 1111 (15)
a & 1 = 1, result += 1
a = a >> 1 = 111
a & 1 = 1, result += 1
a = a >> 1 = 11
a & 1 = 1, result += 1
a = a >> 1 = 1
a & 1 = 1, result += 1
a = a >> 1 = 0
We've got 4 as a result now!
```

There’s a faster (on average) alternative though. You can just substract -1 from a number and it will turn last binary ‘1’ into ‘0’. We can count how many times we dropped 1 from a number and that will be the answer too, e. g.:

This algorithm is faster as it’s runtime complexity is based on a number of ‘1’s in a number, while the first one is based on number of bits in a number, so O(bits) vs O(ones).

Use `a = a & (a - 1)`

to remove the last ‘1’ bit of integer.

Also, in some problems it’s asked to do something with the right-most ‘1’ bit of integer, we can get it separately using `a & ~(a - 1)`

## Advanced tricks

### Given a non-empty array of integers, every element appears three times except for one, which appears exactly once. Find that single one.

This is a trick which one might apply to this problem:

We basically put a number into x container, then move it to y, then move it away completely (see comment for number 3). If you don’t understand how it worked, take a piece of paper and draw the bits. (~0 = 11111111 for 32-bit int, btw).

### Parity Checks problem

Imagine a problem where you need to tell if number of 1 bits in number is odd or even (that’s usually used in ECC memory).

We can apply the same formula we used for counting 1s, but what if we need to do it with a massively scaled up input (e. g. billions of numbers go through our program).

What we can do here (and I actually learned this trick from EPI book) is a lookupTable:

### Swapping bits

We can use XOR to swap two bits. Important thing there is that we need to check if they are different first.

#### Reversing bits

Looks the same way as swap