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 28=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 01112. It is also helpful to become familiar with the two’s-complement representation for negative integers.

The bitwise operations (ANDORXORNOT) 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 ith bit is 1, the ith object is selected).

Table of contents

Our information about bits is broken into three parts:

  • Representation of integers in different bases
  • Bitwise operations
  • Bitmasks

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 ith bit to determine if the ith 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 1011002 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 10110.

One-hundred and one can be written as

10110 = 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 10110

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.

10110 = 1 · 64 + 4 · 8 + 5 · 1 = 1 · 82 + 4 · 81 + 5 · 80 = 1458

In table form:

power 2 1 0
8power 64 8 1
Digits 1 4 5
Contribution +64 +32 +5
Result 10110

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 011001112

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 10310

Because 64 + 32 + 4 + 2 + 1 = 103, the number 011001012 = 10310.

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 2N - 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, 00002 and 10002 would both represent zero!

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

  • The leftmost bit represents -2N-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 010 100 1·(-22) + 0 · 21 + 0 · 20 -410
001 0·(-22) + 0 · 21 + 1 · 20 110  101 1·(-22) + 0 · 21 + 1 · 20 -310
010 0·(-22) + 1 · 21 + 0 · 20 210 110 1·(-22) + 1 · 21 + 0 · 20 -210
011 0·(-22) + 1 · 21 + 1 · 20 310 111 1·(-22) + 1 · 21 + 1 · 20 -110

With 3 bits, we can represent the 23 = 8 values from -4 to 3. An N bit signed integer can represent the values from -2N-1 to +2N-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 ith bit of a variable X as Xi. Then we have the following bitwise operations between two N bit variables X and Y:

  • X & Y (bitwise AND):
    The ith bit of X&Y is equal to AND(Xi, Yi).
  • X | Y (bitwise OR):
    The ith bit of X|Y is equal to OR(Xi, Yi).
  • X ^ Y (bitwise XOR):
    The ith bit of X^Y is equal to XOR(Xi, Yi).

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 → 11010 and  11000110 → 19810:

  • 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 4510 = 001011012, so

     45 << 2  is 101101002 = 18010

    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, 4510 = 001011012, so

     45 >>> 2  is 000010112 = 1110

    Seeing the same result for a signed negative number is useful. We have -4510 = 110100112 so

     -45 >>> 2  is 001101002 = 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 000010112 = 1110

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

Bitmasks

There are many different interpretations possible for what each bit represents. In the introduction, we used the ith bit represents whether the ith 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 ith switch is on, and when bit i is 0 we say the ith switch is off. The 0th bit will be at the right end, and we will count back toward the front. This has the nice property that the ith bit is the coefficient of 2i.

Getting the ith bit / Checking the state of the ith switch

We can find the value of the ith 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 ith position. Therefore n & (1 << i) ensures all bits except the ith 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 ith bit / Turning the ith switch on

We can get a number that is n with the ith 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 ith bit of n is OR-ed with zero, they are all copied into the new variable.

Clearing the ith bit of n/ Turning the ith 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 ith bit, we want to return n & mask.

To generate mask, note that we know how to set only the ith 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 1s, 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 ith bit of n / toggling the ith 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 ith bit of n, we would return n ^ (1 << i).

Updating the ith bit of n to x.

Let’s say that we know x is 1 or 0. How would we use it to set the ith 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 ith bit to zero, then ORs it with 0 (if x is zero) or ORs it with a number with only the ith 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:     

Leave a Reply

X