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’scomplement 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).
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 subsetsum 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 bitstring 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 to1
.0
will give you all bits set to0
.
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 onehundred and one. If we want to be explicit, we can write the base as a subscript, such as 101
_{10}.
Onehundred and one can be written as
101
_{10} = 1 · 100 + 0 · 10 + 1 · 1 = 1 · 10^{2} + 0 · 10^{1} + 1 · 10^{0}
We can summarize this somewhat systematically in a table:
power  2  1  0  

10^{power}  100  10  1  
Digits  1  0  1  
Contribution  +100  0  +1  
Result  101 _{10} 
If we wanted to represent onehundred 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 · 8^{2} + 4 · 8^{1} + 5 · 8^{0} = 145
_{8}
In table form:
power  2  1  0  

8^{power}  64  8  1  
Digits  1  4  5  
Contribution  +64  +32  +5  
Result  101 _{10} 
Nbit unsigned integers
When writing an unsigned number in binary, or base 2, we are expanding it in powers of 2. The i^{th} bit, counted from the right, tells us about how many copies of 2^{i} we would need when expanding our number in powers of two. As an example, to “decode” an 8bit number such as 01100111
_{2}
power  7  6  5  4  3  2  1  0  

2^{power}  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 2^{N} 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).
Nbit signed integers and 2’scomplement
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 4bit 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
^{N1}  The
N1
other bits are interpreted as aN1
bit number.
For example, here are all 3bit signed integers:
Bits  Expansion  #  Bits  Expansion  #  

000  0·(2^{2}) + 0 · 2^{1} + 0 · 2^{0}  0 _{10} 
100  1·(2^{2}) + 0 · 2^{1} + 0 · 2^{0}  4 _{10} 

001  0·(2^{2}) + 0 · 2^{1} + 1 · 2^{0}  1 _{10 } 
101  1·(2^{2}) + 0 · 2^{1} + 1 · 2^{0}  3 _{10} 

010  0·(2^{2}) + 1 · 2^{1} + 0 · 2^{0}  2 _{10} 
110  1·(2^{2}) + 1 · 2^{1} + 0 · 2^{0}  2 _{10} 

011  0·(2^{2}) + 1 · 2^{1} + 1 · 2^{0}  3 _{10} 
111  1·(2^{2}) + 1 · 2^{1} + 1 · 2^{0}  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
^{N1} to +2
^{N1}  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
ifx
andy
are1
, otherwise returns the bit0
.  OR(x,y): Returns the bit
1
if eitherx
ory
(or both) are1
, otherwise returns the bit0
.  XOR(x,y): Returns the bit
1
if only onex
ory
is1
, otherwise returns the bit0
. Called eXclusive OR to rule out both being1
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):
Thei
^{th} bit ofX&Y
is equal toAND(X
_{i}, Y
_{i})
.X  Y
(bitwise OR):
Thei
^{th} bit ofXY
is equal toOR(X
_{i}, Y
_{i})
.X ^ Y
(bitwise XOR):
Thei
^{th} bit ofX^Y
is equal toXOR(X
_{i}, Y
_{i})
.
Given a bit function, we can always define the corresponding bitwise operation that applies the bit function bitbybit. 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
or110 & 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 bitbybit), but they are important enough to be included anyway. They are:
 left shift:
x << n
Takes the variablex
and shifts it to the leftn
bits, filling new spaces on the right with zeros. For example45
_{10}= 00101101
_{2}, so45 << 2
is10110100
_{2}= 180
_{10}The added zeroes have been shown in bold. For programming languages with fixed bit width data types like
short
andlong
, 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 by2<sup>n</sup>
.  (logical) right shift:
x >>> n
Takes the variablex
and shifts it to the rightn
bits, filling the new bits on the left with zeros. For example,45
_{10}= 00101101
_{2}, so45 >>> 2
is00001011
_{2}= 11
_{10}Seeing the same result for a signed negative number is useful. We have
45
_{10}= 11010011
_{2} so45 >>> 2
is00110100
_{2}= 52
When making a logical rightshift of a negative number, the answer will depend on the number of bits that are used to store the integer. Some languages that have variablesized integers (notably Python) don’t have a logical rightshift.
 (arithmetic) right shift:
x >> n
Takes the variablex
and shifts it to the rightn
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
is00001011
_{2}= 11
_{10}For negative numbers, there is a difference. Using the 8 bit signed integer
45
again, we have
45 >> 2
is11110100
_{2}= 12
Bitmasks
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 subsetsum 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. ANDing with zero ignores that bitAND(1,x) = x
, i.e. ANDing 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:
If the `i`^{th} bit is zero, then the output is zero. Checking if the output is nonzero 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. ORing with zero returns the value of the bit.OR(1,x) = 1
, i.e. ORing with one always gives one.
Looking at two examples:
Since every bit except the i
^{th} bit of n
is ORed 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).