Bit manipulation is the direct manipulation of data bits to perform operations and is an important optimization skill now tested by FAANG recruiters. However, this topic is heavily mathematical and is rarely covered in a nonuniversity computer science setting.
Today, we'll give you a tutorial on bit manipulation and explore some handson practice with popular interview questions.
Here’s what we’ll cover today:
 What is bit manipulation?
 Bitwise Operators
 Bitwise Tricks
 Handson practice with Bitwise operators
 What to learn next
Be ready for any bit manipulation question
Practice top asked questions for each bitwise operator with handson coding environments.
Master Solving Problems using Bit Manipulation
What is bit manipulation?
Bit manipulation is the process of applying logical operations on a sequence of bits, the smallest form of data in a computer, to achieve a required result. Bit manipulation has constant time complexity and process in parallel, meaning it is very efficient on all systems.
Most programming languages will have you work with abstractions, like objects or variables, rather than the bits they represent. However, direct bit manipulation is needed to improve performance and reduce error in certain situations.
Bit manipulation requires a strong knowledge of binary and binary conversion.
Here's a few examples of tasks that require bit manipulation:
 Lowlevel device control
 Error detection and correction algorithms
 Data compression
 Encryption algorithms
 Optimization
For example, take a look at the difference between an arithmetic and bit manipulation approach to finding the green portion of an RGB value:
// arithmetic
(rgb / 256) % 256
// bit
(rgb >> 8) & 0xFF
While both do the same thing, the second option is considerably faster, as it works directly within memory rather than through a level of abstraction.
We'll explore what each of these operators do later in this article (>>
and &
).
Bitwise Manipulation and Coding Interviews
Bit manipulation is also a common topic in coding interviews, especially with FAANG companies. These interviewers expect you to have a basic understanding of bits, fundamental bit operators, and generally understand the thought process behind bit manipulation.
Having this knowledge demonstrates that you're a wellrounded developer who understands both the specific tools and the foundation of computer science.
If you're applying for a role that will work with embedded systems or other lowlevel systems, you'll encounter more bit questions. In short, the closer your role is to machine level, the more bit manipulation questions you'll encounter.
The best way to prepare for bit manipulation questions is to practice using each bitwise operator and brush up on your binary to decimal conversions.
Bitwise Operators
Bitwise operations take one or more bit patterns or binary numerals and manipulate them at the bit level. They're essentially our tool to manipulate bits to achieve our operations.
While arithmetic operations perform operations on humanreadable values (1+2
), bitwise operators manipulate the lowlevel data directly.
Advantages
 They are fast and simple actions.
 They are directly supported by the processor.
 They are used to manipulate values for comparisons and calculations.
 Bitwise operations are incredibly simple and faster than arithmetic operations.
Let's take a quick look at each of the major Bitwise operators and their uses.
AND Operator
AND (&
) is a binary operator that compares two operands of equal length. The operands are converted from their readable form to binary representation. For each bit, the operation checks if both bits are 1
across both operands. If yes, that bit is set to 1
in the answer. Otherwise, the corresponding result bit is set to 0.
It essentially multiplies each bit by the corresponding bit in the other operand. As multiplying anything by 0
results in 0
, the AND comparison with any 0
bit will result in 0
.
 If two input bits are 1, the output is 1.
 In all other cases its 0, for example:

1 & 0
=> yields to 0. 
0 & 1
=> yields to 0. 
0 & 0
=> yields to 0.

0101 (decimal 5)
AND 0011 (decimal 3)
0 * 0 = 0
1 * 0 = 0
0 * 1 = 0
1 * 1 = 1
Therefore:
= 0001 (decimal 1)
The operation may be used to determine whether a particular bit is set (1) or clear (0). It's also used to clear selected bits of a register in which each bit represents an individual Boolean state.
class AndOperation {
public static void main( String args[] ) {
int x = 12;
int y = 10;
System.out.println("Bitwise AND of (" + x + " , " + y + ") is: " + (x & y)); // yields to 8
}
}
OR Operator
The OR operator (
) is a binary operator that takes two equallength operands but compares them in the opposite way to AND; if either corresponding bit is 1
, the answer is 1
. Otherwise, the answer will be 0
. In other words, Bitwise OR returns ‘1’ if one of the inputs given is 1
.
 If two input bits are
0
, the output is0
.  In all other cases, it is
1
. For example:
1  0
=> yields to 1. 
0  1
=> yields to 1. 
1  1
=> yields to 1.

a = 12
b = 10

a in Binary : 0000 0000 0000 1100
b in Binary : 0000 0000 0000 1010

a  b : 0000 0000 0000 1110

This is often used as an interim logic step for solving other problems.
class OROperation {
private static int helper(int x, int y) {
return x  y;
}
public static void main(String[] args) {
int x = 12;
int y = 10;
System.out.println("Bitwise OR of " + x + ", " + y + " is: " + helper(x, y)); // yields to 14
}
}
NOT Operator
NOT (~
), or sometimes called the bitwise complement operator, is a unary operation that takes a single input and swaps each bit in its binary representation to the opposite value.
All instances of 0
become 1
, and all instances of 1
become 0
. In other words, NOT inverts each input bit. This inverted sequence is called the one's complement of a bit series.
For example, consider
x = 1
The binary number representation of
x
is:
x = 00000000 00000000 00000000 00000001
Now, Bitwise NOT of
x
will be:
~x = 11111111 11111111 11111111 11111110
So:
x
contains 31 zeros(0's) and one 1~x
contains 31 ones(1's) and one 0(zero)
This makes the number negative as any bit collection that starts with 1
is negative.
NOT is useful for flipping unsigned numbers to the mirrored value on the opposite side of their midpoint.
For 8bit unsigned integers, NOT x = 255  x
.
Formula: ~x = 2^{32}  x
class NOTOperation {
public static void main( String args[] ) {
int a = 1;
System.out.println("Bitwise NOT of a is : " + ~a);
}
}
XOR Operator
The bitwise XOR operation (^
), short for "ExclusiveOr", is a binary operator that takes two input arguments and compares each corresponding bit. If the bits are opposite, the result has a 1
in that bit position. If they match, a 0
is returned.

1 ^ 1
=> yields to 0. 
0 ^ 0
=> yields to 0. 
1 ^ 0
=> yields to 1. 
0 ^ 1
=> yields to 1.
For example:
a = 12
b = 10

a in binary : 0000 0000 0000 1100
b in binary : 0000 0000 0000 1010

a ^ b : 0000 0000 0000 0110

XOR is used to invert selected individual bits in a register or manipulate bit patterns that represent Boolean states.
XOR is also sometimes used to set the value of a registry to zero as XOR with two of the same input will always result in 0
.
class XOROperation {
public static void main( String args[] ) {
int x = 12;
int y = 10;
System.out.println("Bitwise XOR of (x , y) is : " + (x ^ y)); // yields to 6
}
}
Left and right shift operator
A bit shift is a Bitwise operation where the order of a series of bits is moved to efficiently perform a mathematical operation. A bit shift moves each digit in a number’s binary representation left or right by a number of spaces specified by the second operand.
These operators can be applied to integral types such as int
, long
, short
, byte
, or char
.
There are three types of shift:

Left shift:
<<
is the left shift operator and meets both logical and arithmetic shifts’ needs. 
Arithmetic/signed right shift:
>>
is the arithmetic (or signed) right shift operator. 
Logical/unsigned right shift:
>>>
is the logical (or unsigned) right shift operator.
In Java, all integer data types are signed and
<<
and>>
are solely arithmetic shifts.
Here's an example of a left shift:
6 = 00000000 00000000 00000000 00000110
Shifting this bit pattern to the left one position (6 << 1
) results in the number 12:
6 << 1 = 00000000 00000000 00000000 00001100
As you can see, the digits have shifted to the left by one position, and the last digit on the right is filled with a zero. Note that shifting left is equivalent to multiplication by powers of 2.
6 << 1 → 6 * 2^1 → 6 * 2
6 << 3 → 6 * 2^3 → 6 * 8
Welloptimized compilers will use this rule to replace multiplication with shifts whenever possible, as shifts are faster.
class LeftShift {
private static int helper(int number, int i) {
return number << i;// multiplies `number` with 2^i times.
}
public static void main(String[] args) {
int number = 100;
System.out.println(number + " shifted 1 position left, yields to " + helper(number, 1));
System.out.println(number + " shifted 2 positions left, yields to " + helper(number, 2));
System.out.println(number + " shifted 3 positions left, yields to " + helper(number, 3));
System.out.println(number + " shifted 4 positions left, yields to " + helper(number, 4));
}
}
With right shift, you can either do arithmetic (>>
) or logical (>>
) shift.
The difference is that arithmetic shifts maintain the same most significant bit (MSB) or sign bit, the leftmost bit which determines if a number is positive or negative.
1011 0101 >> 1 = **1**101 1010
Formula: x >> y = x/(2^y)
On the other hand, a logical shift simply moves everything to the right and replaces the MSB with a 0
.
1011 0101 >>> 1 = 0101 1010
Formula: a >>> b = a/(2^b)
Keep learning bit manipulation.
Prepare for FAANG bit manipulation questions in half the time. Educative's interview prep courses let you set yourself up for success with handson practice with the most asked interview questions.
Master Solving Problems using Bit Manipulation
Bitwise Tricks
Now, let's look at a few tricks you can do using bitwise operators.
These are often used as interview questions to check if you've reviewed basic bit manipulation and can apply it to daytoday coding tasks.
Check if a number is even
This one tests your knowledge of how AND works and how even/odd numbers differ in binary. You can simply use:
(x & 1 ) == 0
0110 (6)
& 0001
= 0000 TRUE
This solution relies on two things:

2
equates to0001
 The rightmost number for all odd numbers greater than 2 is
1
Any time the final bit evaluates to 1
, you know that it matched and is, therefore, an odd number. If it instead evaluates to 0
, you know that no numbers matched and therefore it's even.
Convert characters to uppercase or lowercase
This trick tests your knowledge of uppercase and lowercase characters in binary. You can convert any character, ch
, to the opposite case using ch ^= 32
.
This is because the binary representation of lowercase and uppercase letters are nearly identical, with only 1 bit of difference.
Using the XOR operation lets us toggle that single bit and swap it to the opposite value, therefore making a lowercase character uppercase or vice versa.
public class Test
{
static int x=32;
// tOGGLE cASE = swaps CAPS to lower
// case and lower case to CAPS
static String toggleCase(char[] a)
{
for (int i=0; i<a.length; i++) {
// Bitwise XOR with 32
a[i]^=32;
}
return new String(a);
}
/* Driver program */
public static void main(String[] args)
{
String str = "CheRrY";
System.out.print("Toggle case: ");
str = toggleCase(str.toCharArray());
System.out.println(str);
System.out.print("Original string: ");
str = toggleCase(str.toCharArray());
System.out.println(str);
}
}
Handson practice with Bitwise Operators
Now, let's have some handson practice with these operators.
AND Challenge: Count set bits
Write a Java program to count the number of bits set to 1 (set bits) of an integer.
Solution and Explanation
class CountSetBit {
private static int helper(int n) {
int count = 0;
while (n > 0) {
n &= (n  1);
count++;
}
return count;
}
public static void main(String[] args) {
int number = 125;
System.out.println("SetBit Count is : " + helper(number));
}
}
In this approach, we count only the set bits. So,
 If a number has 2 set bits, then the while loop runs two times.
 If a number has 4 set bits, then the while loop runs four times.
Our while loop iterates until n = 0
, dividing by 2 each time via the AND operator. On pass 1, 125
becomes 62
, and count
increases by 1. On the second pass, 62
becomes 31
, and the count increases to 2. This continues until n
becomes 0 and the count is then returned.
Bitwise OR: Number of Flips
Write a program that takes 3 integers and uses the lowest number of flips to make the sum of the first two numbers equal to the third. The program will return the number of flips required.
A flip is changing one single bit to the opposite value ie.
1 > 0
or0 > 1
.
Input: a = 2
, b = 6
, c = 5
Output: 3
Solution and Explanation
class MinFlips {
private static int helper(int a, int b, int c) {
int ans = 0;
for (int i = 0; i < 32; i++) {
int bitC = ((c >> i) & 1);
int bitA = ((a >> i) & 1);
int bitB = ((b >> i) & 1);
if ((bitA  bitB) != bitC) {
ans += (bitC == 0) ? (bitA == 1 && bitB == 1) ? 2 : 1 : 1;
}
}
return ans;
}
public static void main(String[] args) {
int a = 2;
int b = 6;
int c = 5;
System.out.println("Min Flips required to make two numbers equal to third is : " + helper(a, b, c));
}
}
First, we initialize ans
to 0
. Then we loop through from a range of 0  31. We initialize bitA
, bitB
, and bitC
to equal our right shift formula ANDed with 1:
(a/(2^i) & 1
Then, we check if bitA  bitB
equals bitC
. If yes, we move on to check if bitC = 0
. From there, if bitA = 1
and bitB = 1
then we increase ans
by 2. Otherwise, we increase ans
by 1.
Finally, we return ans
, which has increased by one on every operation.
Bitwise XOR: Single Number
Find the element in an array that is not repeated.
Input: nums = { 4, 1, 2, 9, 1, 4, 2 }
Output: 9
Solution and Explanation
class SingleNumber {
private static int singleNumber(int[] nums) {
int xor = 0;
for (int num : nums) {
xor ^= num;
}
return xor;
}
public static void main(String[] args) {
int[] nums = {4, 1, 2, 9, 1, 4, 2};
System.out.println("Element appearing one time is " + singleNumber(nums));
}
}
This solution relies on the following logic:
 If we take XOR of zero and some bit, it will return that bit:
a ^ 0 = a
 If we take XOR of two same bits, it will return 0:
a ^ a = 0
 For n numbers, the below math can be applied:
a ^ b ^ a = (a ^ a) ^ b = 0 ^ b = b
For example,
1 ^ 5 ^ 1 =
(1 ^ 1) ^ 5 =
0 ^ 5 = 5
Therefore, we can XOR all bits together to find the unique number.
Bitwise Left Shift: Get First Set Bit
Given an integer, find the position of the first setbit (1
) from the right.
Input: n = 18
18 in binary = 0b10010
Output: 2
Solution and Explanation
class FirstSetBitPosition {
private static int helper(int n) {
if (n == 0) {
return 0;
}
int k = 1;
while (true) {
if ((n & (1 << (k  1))) == 0) {
k++;
} else {
return k;
}
}
}
public static void main(String[] args) {
System.out.println("First setbit position for number: 18 is > " + helper(18));
System.out.println("First setbit position for number: 5 is > " + helper(5));
System.out.println("First setbit position for number: 32 is > " + helper(32));
}
}
The logic of this solution relies on a combination of left shifting and the AND operation.
Essentially, we first check if the rightmost significant bit is the set bet using bit & 1
. If not, we keep shifting left and checking until we find the bit that makes our AND operation yield 1
.
The number of shifts is tracked by our pointer, k
. Once we do find the set bit, we return k
as our answer.
What to learn next
Congratulations on finishing our bit manipulation quick guide! Bit manipulation can be a tricky topic to learn, but handson practice is the best way to improve.
As you look for more practice, check out these practice problems:
 Find the missing number
 Find the first set bit using right shifting
 Count the number of digits in an integer
 Check if a number is a power of 2
To help you practice these and other bit manipulation interview questions, Educative has created Master Solving Problems using Bit Manipulation. This course will help you refresh your knowledge of binary conversions as well as tons of handson interview question practice.
By the end of the course, you'll know efficient solutions to all the top bit manipulation interview questions asked by FAANG recruiters.
Happy learning!
Top comments (0)