# Bits Interview Essentials

Binary digits, or bits, are variables that can hold two values: `0` or `1`. Bits are grouped together in bytes, which is the smallest amount memory that can be allocated. Most interviewers will allow you to assume there are 8 bits in a byte, so each byte can have one of `2`8`=256` possible values.

Some interviewers will ask you to solve problems that are explicitly about manipulating bits. For these questions, it’s helpful to know how integers are represented in binary, so that you can recognize that `7` is `0111`2. It is also helpful to become familiar with the two’s-complement representation for negative integers.

The bitwise operations (`AND``OR``XOR``NOT`) can be incredibly useful even when the task is not explicitly about bits. Bitwise operations are incredibly fast, and you can compress N yes/no decisions into N bits (rather than N bytes if we stored the numbers `0` and `1` for each decision).

Bitwise operations are particularly useful when doing image manipulation, or implementing the hash functions of hash tables. An advanced use of bits is often used in dynamic programming when looking at which of `N` objects we are going to select, as we can use an `N` bit integer to represent which objects were selected (if the `i`th bit is 1, the `i`th object is selected).

Our information about bits is broken into three parts:

• Representation of integers in different bases
• Bitwise operations

Many applications of bits don’t actually require you to think about them as integers. Individual bits can be used to represent a decision. For example, the subset-sum problem asks if there is a subset of a given set that add to a given number. As an example, is there a subset of `{ 2, 3, 4, 6, 21, 14}` that sums to 12? One way of arranging the elements in an array (sets have no order!) and labeling the subsets by using the `i`th bit to determine if the `i`th element was in the subset or not. For example, the subset `{2, 4, 6}` (which does sum to 12) can be represented as the bit-string `101100` because

Element index 2 3 4 6 21 14
Subset bitmask 1 0 1 1 0 0

In order to use bits this way, and effectively manipulate the bits, it is important to know bitmasks, which in turn depend on bitwise operations. It is not as important to know that most programs think of `101100`2 as the number `44`.

We have included how integers are represented as bits because:

• When debugging, it is convenient to be able to print out your bitmask and interpret it.
• There are problems where we are using bits to determine the properties of numbers (e.g. determining if a number `n` is a power of 2 or not can be done very quickly using bitmasks).
• Interviewers may ask general knowledge questions about how bits are arranged.

What you really need to know about integers is

• `-1` will give you all bits set to `1`.
• `0` will give you all bits set to `0`.

## Integer representations in different bases

#### Getting familiar with bases mathematically.

The most familiar representation of integers is in base 10 (i.e. using 10 digits, 0 through 9), with an optional sign in front. The sign will be treated a little bit differently when coding `N` bit integers. Because this is the “normal” way of representing a number, we often explicitly say that the number is written in base 10. When we see the number `101`, we generally assume it is one-hundred and one. If we want to be explicit, we can write the base as a subscript, such as `101`10.

One-hundred and one can be written as

`101`10 = 1 · 100 + 0 · 10 + 1 · 1 = 1 · 102 + 0 · 101 + 1 · 100

We can summarize this somewhat systematically in a table:

power 2 1 0
10power 100 10 1
Digits 1 0 1
Contribution +100 0 +1
Result `101`10

If we wanted to represent one-hundred and one in powers of 8, for example, we would look at the powers of 8 that are less than 101, namely 1, 8, and 64. Each digit can take 8 values (0 through 7), so we know a number written in base 8 will never have an 8 or 9 in it.

`101`10 = 1 · 64 + 4 · 8 + 5 · 1 = 1 · 82 + 4 · 81 + 5 · 80 = `145`8

In table form:

power 2 1 0
8power 64 8 1
Digits 1 4 5
Contribution +64 +32 +5
Result `101`10

#### N-bit unsigned integers

When writing an unsigned number in binary, or base 2, we are expanding it in powers of 2. The ith bit, counted from the right, tells us about how many copies of 2i we would need when expanding our number in powers of two. As an example, to “decode” an 8-bit number such as `01100111`2

power 7 6 5 4 3 2 1 0
2power 128 64 32 16 8 4 2 1
Binary digits 0 1 1 0 0 1 1 1
Contribution 0 +64 +32 0 0 +4 +2 +1
Result `103`10

Because `64 + 32 + 4 + 2 + 1 = 103`, the number `01100101`2` = 103`10.

If the number of bits is fixed (as it for the `short` and `long` datatypes in C/C++/Java) at `N` then we can only represent 2N different values. The smallest number that can be represented is `0` (where all bits are zero), and the highest number that can be represented is `2`N` - 1` (where all the bits are set to one).

#### N-bit signed integers and 2’s-complement

An “obvious” way of representing negative numbers would be to have the leftmost bit be `0` for a positive number and `1` for a negative number, much like the ± signs used in math. This encoding isn’t widely used because it gives the number `0` two encodings. Demonstrating with 4-bit integers, `0000`2 and `1000`2 would both represent zero!

The standard encoding method is called the two’s complement, which works in the following way:

• The leftmost bit represents `-2`N-1
• The `N-1` other bits are interpreted as a `N-1` bit number.

For example, here are all 3-bit signed integers:

Bits Expansion # Bits Expansion #
000 0·(-22) + 0 · 21 + 0 · 20 `0`10 100 1·(-22) + 0 · 21 + 0 · 20 `-4`10
001 0·(-22) + 0 · 21 + 1 · 20 `1`10  101 1·(-22) + 0 · 21 + 1 · 20 `-3`10
010 0·(-22) + 1 · 21 + 0 · 20 `2`10 110 1·(-22) + 1 · 21 + 0 · 20 `-2`10
011 0·(-22) + 1 · 21 + 1 · 20 `3`10 111 1·(-22) + 1 · 21 + 1 · 20 `-1`10

With 3 bits, we can represent the `2`3` = 8` values from `-4` to `3`. An N bit signed integer can represent the values from `-2`N-1 to `+2`N-1` - 1`.

## Bitwise operations

The binary bit function is any function that takes two bits, and returns a single bit. It is common to refer to a bit being `1` as `True`, and a bit being `0` as `False`. If `x` and `y` are individual bits, then here are the most common binary bit functions:

• AND(x,y): Returns the bit `1` if `x` and `y` are `1`, otherwise returns the bit `0`.
• OR(x,y): Returns the bit `1` if either `x` or `y` (or both) are `1`, otherwise returns the bit `0`.
• XOR(x,y): Returns the bit `1` if only one `x` or `y` is `1`, otherwise returns the bit `0`. Called eXclusive OR to rule out both being `1` as an option.

Table of bitwise operations

x y OR(x,y) AND(x,y) XOR(x,y)
0 0 0 0 0
0 1 1 0 1
1 0 1 0 1
1 1 1 1 0

Most variables we deal with have multiple bits. For convenience, we label the `i`th bit of a variable `X` as `X`i. Then we have the following bitwise operations between two `N` bit variables `X` and `Y`:

• `X & Y` (bitwise AND):
The `i`th bit of `X&Y` is equal to `AND(X`i`, Y`i`)`.
• `X | Y` (bitwise OR):
The `i`th bit of `X|Y` is equal to `OR(X`i`, Y`i`)`.
• `X ^ Y` (bitwise XOR):
The `i`th bit of `X^Y` is equal to `XOR(X`i`, Y`i`)`.

Given a bit function, we can always define the corresponding bitwise operation that applies the bit function bit-by-bit. As an example, let’s apply each of these bitwise operations to the 8 bit unsigned ints `01101110 → 110`10 and ` 11000110 → 198`10:

• Example of bitwise AND: `01101110 & 11000110 = 01000110` or `110 & 198 = 70`
``````
01101110
& 11000110
==========
01000110
``````

* Example of bitwise OR: `01101110 | 11000110 = 11101110` or `110 | 198 = 238`

``````
01101110
| 11000110
==========
11101110
``````

* Example of bitwise XOR: `01101110 ^ 11000110 = 10101000` or `110 ^ 198 = 168`

``````
01101110
^ 11000110
==========
10101000
``````

In addition to the binary bitwise operations `&``|`, and `^`, there is the bitwise NOT operator (usually referred to as `~` in programming languages). As the name suggests, every bit in `~X` is different from the corresponding bit in `X`.

#### Bit shifting

Our last operations aren’t really bitwise operations (they don’t perform operations bit-by-bit), but they are important enough to be included anyway. They are:

• left shift: `x << n`
Takes the variable `x` and shifts it to the left `n` bits, filling new spaces on the right with zeros. For example `45`10` = 00101101`2, so

` 45 << 2 ` is `10110100`2` = 180`10

The added zeroes have been shown in bold. For programming languages with fixed bit width data types like `short` and `long`, bits that get shifted too far to the right are dropped. Other programming languages like Python return an object with a greater number of bits.

Left shifting an integer by `n` is the same as multiplying by `2<sup>n</sup>`.

• (logical) right shift: `x >>> n`
Takes the variable `x` and shifts it to the right `n` bits, filling the new bits on the left with zeros. For example, `45`10` = 00101101`2, so

` 45 >>> 2 ` is `00001011`2` = 11`10

Seeing the same result for a signed negative number is useful. We have `-45`10` = 11010011`2 so

` -45 >>> 2 ` is `00110100`2` = 52`

When making a logical right-shift of a negative number, the answer will depend on the number of bits that are used to store the integer. Some languages that have variable-sized integers (notably Python) don’t have a logical right-shift.

• (arithmetic) right shift: `x >> n`
Takes the variable `x` and shifts it to the right `n` bits, filling new bits on the left with whatever is contained in the leftmost bit. For positive numbers, the leftmost bit is zero, so the arithmetic and logical right shifts are the same:

` 45 >> 2 ` is `00001011`2` = 11`10

For negative numbers, there is a difference. Using the 8 bit signed integer `-45` again, we have
` -45 >> 2 ` is `11110100`2` = -12`

There are many different interpretations possible for what each bit represents. In the introduction, we used the `i`th bit represents whether the `i`th element was in the subset for the subset-sum problem.

For bitmasks we’ll make an analogy to a switch, where if bit `i` is 1 we say the `i`th switch is on, and when bit `i` is 0 we say the `i`th switch is off. The `0`th bit will be at the right end, and we will count back toward the front. This has the nice property that the `i`th bit is the coefficient of `2`i.

#### Getting the `i`th bit / Checking the state of the `i`th switch

We can find the value of the `i`th bit of `n` by using `(n & (1 << i)) != 0`. Can you see why it works?

We use the following properties of the `AND` function:

• `AND(0,x) = 0`, i.e. AND-ing with zero ignores that bit
• `AND(1,x) = x`, i.e. AND-ing with one returns the value of the bit

The number `1 << i` is the number with `0` everywhere, except for a one in the `i`th position. Therefore `n & (1 << i)` ensures all bits except the `i`th bit is zero. Looking at an example for finding the 4th or 3rd bit:

11010001 n & 00010000 (1<<4) ==========   00010000 (n & ( 1 << 4))
11010001 n & 00001000 (1<<3) ==========   00000000 (n & ( 1 << 3))

If the `i`th bit is zero, then the output is zero. Checking if the output is non-zero will tell us the value of the `i`th bit.

#### Setting the `i`th bit / Turning the `i`th switch on

We can get a number that is `n` with the `i`th position changed to `1` with the code `n | ( 1 << i )`. Can you see why it works?

We are using the following properties to the `OR` function:

• `OR(0,x) = x`, i.e. OR-ing with zero returns the value of the bit.
• `OR(1,x) = 1`, i.e. OR-ing with one always gives one.

Looking at two examples:

11010001 n | 00010000 (1<<4) ==========   11010001 (n | ( 1 << 4))
11010001 n | 00001000 (1<<3) ==========   11011001 (n | ( 1 << 3))

Since every bit except the `i`th bit of `n` is OR-ed with zero, they are all copied into the new variable.

#### Clearing the `i`th bit of `n`/ Turning the `i`th switch off.

We can force a bit to zero using `AND(0,x) = 0`. We can preserve the other bits by using `AND(1,x) = x`. So if we can make a number `mask` that has all of its bits as `1` except the `i`th bit, we want to return `n & mask`.

To generate `mask`, note that we know how to set only the `i`th bit with `(1 << i)`. We want the bitwise NOT of this: `mask = ~(1 << i)`.

So our final result is `n & (~ (1 << i))`.

#### Clearing the `i` least significant bits of `n`/ Turning the first `i` switches off.

This is interesting as it shows how to set multiple values at once. We are interested in switching off the `i` rightmost (i.e. lowest power of 2) bits to zero. Forcing bits to zero suggests using AND. Ideally we would make a `mask = 1111..100000` where the rightmost `i` bits were zero, and all the others were one. Then our answer would be `n & mask`.

How do we create `mask`? If we start with a variable that is all `1`s, then we can left shift it `i` times to get the `i` rightmost bits set to `0`. The number that has all of its bits set to one for a signed int is `-1`. So `mask = (-1 << i)`.

Our final result is `n & (-1 << i)`.

#### Toggle the `i`th bit of `n` / toggling the `i`th switch

XOR is great here. Like OR, `XOR(0,x) = x` so we can use a mask with zero bits to preserve the bits we want to leave alone. We also have `XOR(1,x) = NOT(x)`! In fact, we can use this toggle property to eliminate the `~` operator altogether, because `~X` is the same as `X ^ (-1)`.

To toggle the `i`th bit of `n`, we would return `n ^ (1 << i)`.

#### Updating the `i`th bit of `n` to `x`.

Let’s say that we know `x` is 1 or 0. How would we use it to set the `i`th bit to `x`, given that we used AND to clear the bit (set it to `0`) but OR to set the bit (set it to `1`)?

Here is one approach for what to return `(n & (~(1 << i))) | (x << i)`. What this does is force the `i`th bit to zero, then ORs it with `0` (if `x` is zero) or ORs it with a number with only the `i`th bit set, forcing that bit to 1 if `x` is 1.

## Final comments on bits in Interviews

This is one of the longer overviews! There is a lot of background detail, and bit problems are generally very compact. The hard part isn’t the length of the code that you’re writing, but becoming comfortable thinking in bits, knowing some standard tricks, and getting a feel for when to use OR (forcing a bit to `1`), AND (forcing a bit to `0`), or XOR (forcing a bit to toggle).

Tagged on: