.svg)
.svg)
Getting ready for an Embedded Software Engineering interview? This article is specifically designed for Embedded Software Engineers looking to practice or brush up on their bit manipulation skills. We will cover the basics of Bitwise operators and look at some of the most vital bit manipulation operations. We’ll also go through examples of important bit manipulation interview questions.
Prerequisites:
- C / Embedded C or any related programming language
- Binary number representation
Here’s what we cover:
- What Is Bit Manipulation?
- Bit Manipulation in C: Bitwise Operators
- Bit Manipulation Interview Questions
- Bonus Resources for Embedded Software Engineers
- FAQs on Bit Manipulation
What Is Bit Manipulation?
Data and information are represented as a computer's sequence of bits or Bytes. For most tasks, modern programming languages allow the programmer to work directly with abstract data types such as float, double, integer etc., instead of bits that represent those abstractions. At the same time, the source code does the manipulation on bits.
In many cases, solving problems with bit manipulation can give many-fold speed-ups. An Embedded Software Engineer is often supposed to go one level deep and manipulate the bit sequence directly to efficient code algorithms.
Some tasks that require bit manipulation include:
- Low-level device control
- Communication protocols
- Data compression
- Encryption
- Error detection
- Correction algorithms
- Data compression
How Important Is Bit Manipulation Embedded Software Engineering Interviews?
Embedded Software Engineers are required to work in resource-constrained environments while working with low-level software development. Hence, an in-depth understanding of binary representation in computer systems and bit manipulation is essential for anyone who wants to work on developing Embedded Systems. Bit manipulation is also an essential part of any Embedded System interviews.
Bit Manipulation in C: Bitwise Operators
Let’s start by going through some essential Bitwise operations. Understanding these operations is very important as these are used in most bit manipulation techniques. Note that we will use C (Embedded C) as the programming language in the code snippets throughout the blog.
Bitwise Operator #1: AND(&)
It is denoted by the symbol ‘&’. Bitwise AND compares two operands(bits) and returns ‘1’ at places where both operands are 1. It returns 0 if both operands are 0 or different from each other. Let’s look at the example below; the expression 0xA3 & 0x79 returns 0x21.
Bitwise Operator #2: OR(|)
It is denoted by the symbol ‘|’. Bitwise OR compares two operands(bits) and returns ‘1’ at places where any of the operands is 1. It returns 0 if both operands are 0. See the example below; the expression 0xA3 | 0x79 returns 0xFB.
Bitwise Operator #3: NOT(~)
Unlike AND and OR, NOT is a unary operator which can be applied to one operand at a time. NOT is denoted by the symbol ‘~’. It simply inverts the bit from 0 to 1 and vice versa. Look at the example below; the expression ~0xA3 returns 0x5C.
Bitwise Operator #4: XOR(^)
The bitwise XOR is denoted by ‘^’. XOR is short for Exclusive OR; it is crucial in bit manipulation use cases. You will come across many bit manipulation problems based on Exclusive OR operation.
The bitwise XOR operation returns 1 at places where the two operands(bits) are different, i.e. 1^0 = 1, 0^1 = 1. Otherwise, it returns 0 at places where both the bits are the same(0/1). See the example below; the expression 0xA3 ^ 0x79 returns 0xDA.
Bitwise Operator #5: Right Shift and Left Shift
Now let’s understand the two-bit shift operators. Right, and left shift operators are used to shifting bits right or left side, respectively, by a given number. For simplicity, in this blog, we will be talking about these bitwise shift operators for unsigned numbers.
The Right shift operator is detonated by the symbol ‘>>’. The Right shift expression ‘x >> n’ means to shift the bits of the number ‘x’(assume it is an unsigned integer) to the right by the number of steps specified by the integer ‘n’. Internally the leftmost ‘n’ bits of the number ‘x’ will be discarded, and the ‘n’ number of 0s will be appended on the right. Let’s look at the example below.
?00110011 >> 4 = 00000011
If you look closely, the right shift operator is similar to dividing the operand by two, n times. This is true for unsigned integers.
Similarly, the left shift operator is detonated by the symbol ‘<<’. The left shift expression ‘x << n’ means to shift the bits of the number ‘x’(assume it is an unsigned integer) to the left by the number of steps specified by the integer ‘n’. Internally the rightmost ‘n’ bits of the number ‘x’ will be discarded, and the ‘n’ number of 0s will be appended from the left. Let’s look at the example below.
?00110011 << 4 = 00110000
If you look closely, the left shift operator is similar to multiplying the operand by two n times.
?Homework: You have understood the bitwise shift operations for unsigned numbers. Now, what about signed numbers? Can you find out the effect of bit-wise shift operators in signed numbers?
Bitwise Operator #6: Bit Masking
Having understood the basic bit-wise operators, let’s advance our knowledge and understand bit masking. In bit masking, the ‘masking’ can be understood as hiding or showing some information. Bit masking is applying a mask over a value to keep, change or retrieve selective bit/s without affecting the other bits. A mask determines which bits to clear, set or maintain off a given binary sequence.
Bit masking is an essential concept to learn for any programmer. Bit masking finds its use cases in areas like image processing as well. Embedded Software Engineers use many bit masking techniques when working with microcontrollers as they often modify, read and update their registers.
Now, let’s look at some examples of bit masking to understand it better.
Setting a Bit
Let’s start bit masking by learning to set a particular bit in a given sequence. For this example, let’s assume you have an 8-bit sequence bs = 10110111, and you are asked to set the 6th index bit (zero-indexed, starting from the right).
To do that, we first need to create an appropriate mask and decide the bitwise operation we want to use. Since ‘OR’ of 0 with any bit(1/0) results in the same bit, and 0|1 = 1, it seems the ‘OR’ operation would be appropriate to use here. This will ensure that we don’t change any other bit in the sequence.
Our mask would be 01000000 - which we can create using the left shift operation. Hence the solution looks like the one below.
Clearing a Bit
Having understood the technique to set the bit, let’s see how we can clear a particular bit in a given bit sequence. For this example, let’s assume you have an 8-bit sequence bs = 10110111, and you are asked to clear the 2nd index bit.
So this time, we will use ‘AND’ as the operator with this 11111011-bit mask. We use a similar technique of creating this bit mask by using the left shift operation, but we will also invert the bits.
~(1<<3) = ~(00000100) = 11111011
Finally, we perform the bitwise AND operation on bs to set off the 2nd index(3rd bit) bit.
Inverting a Bit
This can also be referred to as toggling a bit, i.e. if the bit at the given location is 0, make it one, and if it is 1, make it 0.
What operator do we use this time?
We will use the Exclusive OR operator ‘XOR’ for this task. For example, let’s again assume you have an 8-bit sequence as bs = 10110111, and you are asked to toggle the 1st indexed bit(2nd bit).
We start by creating a mask. Since we know that 0^1 = 1 and 1^1 = 0, we will create a mask with the 1st indexed bit(2nd bit) as one and all other bits as 0. We use the left shift operation as we used earlier and perform the XOR operation.
Testing a Bit
Now, assume a scenario where you need to perform a specific operation based on the value of a particular bit in a given bit sequence(byte). This is a very common situation when you are working with microcontrollers and need to perform some operations based on the value of a register flag.
To achieve this, we do something opposite to what we had done while clearing a bit but with a twist. This time we allow the bit we are interested in to maintain, but we set all the other bits to zero. This way, if the bit we are looking for is 1, the resulting number from the bit sequence will be greater than 0; otherwise, it will be 0.
Assume you have an 8-bit sequence bs = 10110111, and you are asked to check the 4th indexed(5th bit).
So, we start by creating a mask. We will use the ‘AND’ operation for this; we use the left shift operator to set the 5th bit and then perform the ‘AND’ operation in an IF condition.
if(bs & (1<<5) != 0){
...
}else{
...
}
In the above example, the if block gets executed if the 5th bit of bs is 1; otherwise, the code inside the else block gets executed.
Extracting a Bit
In this situation, you are asked to extract bits between two given points(indexes) in a given bit sequence. Let’s understand this with an example, assume you have an 8-bit sequence bs = 10110111, and you are asked to extract the bits between the 2nd through 6th position(10110111 => 01101 ).
How will you do this?
This will be a two-step task.
We first start by creating a mask. With our mask, we want to maintain the bits 2nd through 6th position and set the rest of the bits to 0. We apply this mask using the ‘AND’ operation, and once we have the bits, we shift them by two places to the left to finally adjust the value.
Monitoring a Bit
The final bitwise operation we will discuss is monitoring. This is very similar to testing a bit that you saw earlier. This situation is also very common in Embedded Systems when you have to constantly monitor the status of certain register flags on a microcontroller. One typical example of this situation is monitoring an interrupt flag bit. These bits are set by the hardware and must be monitored to proceed with the interrupt service routine(ISR) execution.
The mask for monitoring is very similar to testing a bit; we use the same ‘AND’ operation with a similar mask, But this time we will be in a while loop for constant monitoring instead of an if-else statement.
Assume you have an 8-bit sequence bs = 10110111, and you are asked to monitor the 6th index(7th bit). The code goes something like the following.
while(bs & (1<<7) != 0){
…
}
In the above code, the loop executes until the 7th bit of bs is 1.
You can do a lot with these simple-looking bitwise operators. Check out the following thread on StackOverflow: the use-case of the bitwise operators.
Bit Manipulation Interview Questions
Now, let’s go through some of the important bit manipulation interview questions.
1. Hamming Weight of a Number
Hamming weight of a number is also referred to as the number of set bits(1s) in its binary representation.
For this problem, assume that you are given an unsigned integer, and you are asked to implement a function which returns the count of its set bits.
We solve this problem using bitwise operations we have learned so far - masking and shifting or bit extraction. The technique is as follows.
- Keep shifting the bits to the right one at a time and extract the rightmost bit.
- If the extracted bit is 1 - we update our count variable; otherwise, we move on.
- We keep doing the above two steps until our input number becomes 0 or no set bit remains.
Following is the code for your reference. (Embedded C)
2. Power of 2
Given an unsigned integer, you are asked to find if it is a power of 2.
To solve this problem by manipulating its bits, you need to see if there is anything special about the numbers, which are powers of two.
It turns out there is!
Any power of 2 numbers will have exactly one set bit. Hence, if the hamming weight of the given number is 1, then it is a power of 2. Please note this solution works for an unsigned integer.
We have already seen the code to get the hamming weight of the number, so we call the method this time.
Is that all we can do?
No! This problem can also be solved in constant time using bit masking. We use the following expression.
(input & (input-1)) == 0
Let’s understand with an example.
Let’s say input =00001000 (binary).
Now, input - 1 = 00000111.
As powers of 2 numbers are only supposed to have one set bit, the above expression will return in 0, confirming that it is a power of 2. Otherwise, the expression will return something non-zero. So now our O(1) solution is as follows.
Pro tip: Often interviewers probe the candidates to know whether they mugged up tricks like the above from a prep website like Leetcode or if they really understood the concept. So make sure you really understand the logic behind the above expression so that you are able to answer follow-up questions like - what is the insight behind this trick? How did you arrive at this magic expression?
3. Flipping bits to Convert A to B
Now, for this problem, you are given two integers, A and B, and you are asked to count the number of bits you need to flip to convert A into B.
In other words, we need to count the bits which are non-equal between A and B; these are the bits you will have to flip to convert A to B or vice versa.
Hence, we first use the XOR of A and B to only get the different bits and then count the set number of bits(hamming weight). Following is the code for your reference. (Embedded C)
4. Swap all odd and even bits
In this kind of problem, you are given a number(binary sequence) and asked to swap all even and odd bits.
For example: - if the given binary sequence is 00010111, then your output should be 00101011
There are many ways to solve this problem, but we will focus on an efficient bit manipulation-based approach.
In this approach, we first use appropriate masks to extract even and odd bits into separate variables, even_bits & odd_bits, respectively. Now to swap the positions, we right-shift the even_bits and left-shift the odd_bits by one position each. This way, we have the bits in the correct desired positions. We combine the even_bits and odd_bits using the OR operation and get our final result. Following is the code for your reference. (Embedded C)
5. Swap two numbers without using any extra variable.
So for this question, you are given two values, A and B, and you are asked to swap their values without using extra variables. There are many ways to solve this problem, but we will focus on one involving bit manipulation.
For this problem, we need to recall one fundamental property of XOR: it undoes the first application when applying the same input a second time.
That means (a^b)^b = a. So we use this logic to solve the problem using the below code.
6. Swap two bits in given locations.
Given an integer 'n' and two positions, i and j, you must swap the ith and jth bits of the number n.
Can you think of a solution to this problem?
You can solve this problem using the same logic we used in the last problem. The property of XOR - (a^b)^b = a or (a^b)^a = b.
So this time, we first extract the ith and jth bit and perform XOR. We then shift this XOR result in both the ith and jth positions to create a mask. We take this mask and complete the final XOR with the number n to get our final result.
Following is the code implementation for this logic.
Bonus Resources for Embedded Software Engineers
For all the Embedded Software Engineers out there, the following are some bonus Tier-1 interview questions on bit manipulation that you must practice before your following interview. Our Embedded Software Engineering student community submitted these problems and was asked in their tier-1 job interviews.
- Big endian to little endian conversion on a 1024-bit system.
- Does the given code require a change in endianness?
- How to read a 128-bit timestamp on 64-bit architecture?
- Given an 8-bit pattern, find the pattern in the bitstream and return the bit offset.
- Write a function that swaps the highest bits in each nibble of the byte.
- What is the size of the integer variable on 32-bit and 64-bit machines?
- Count bytes in the buffer.
- Find the maximum of two numbers without using comparison or branching.
FAQs on Bit Manipulation
1. What is bit manipulation?
Bit manipulation refers to the practice of manipulating individual bits of data stored in a computer's memory. This is done using bitwise operators, such as AND, OR, XOR, and NOT, to manipulate the binary representation of data. Bit manipulation can be used to set, clear, or toggle specific bits in a variable, as well as to perform bit-shifting operations.
Embedded systems often have limited resources, so bit manipulation can be a useful technique for optimizing code and saving memory. For example, a bit field can be used to store multiple Boolean values using a single byte of memory, rather than using one byte per value.
Bit manipulation can also be useful when working with devices or peripherals that communicate using a serial protocol, such as I2C or SPI, where data is transferred one bit at a time. It can also be useful when working with low-level system control registers.
It is important to note that bit manipulation can be difficult to understand and debug, and it can lead to hard-to-find bugs if not used carefully.
2. What is bitwise?
Bitwise is a term used to describe operations that are performed on the individual bits of a binary number, rather than on the whole number. These operations are performed using bitwise operators, such as AND, OR, XOR, and NOT.
These operators work by comparing each bit of one number to the corresponding bit of another number and applying a logical operation to the pair of bits. The result of the operation is a new number, in which each bit is the result of the operation applied to the corresponding pair of bits from the original numbers.
3. When to use bitwise operators?
Bitwise operators are used in situations where it is necessary to manipulate individual bits of data, rather than working with the entire value. Some common use cases include
- Optimization: Bitwise operations can be faster and use less memory than equivalent operations performed using standard arithmetic operators.
- Bit manipulation: Bitwise operators can be used to set, clear, or toggle specific bits in a variable, which is useful when working with low-level system control registers or devices that communicate using a serial protocol.
- Bit fields: Bitwise operators can be used to create bit fields, which are groups of bits within a larger data type that can be used to store multiple Boolean values using a single byte of memory.
- Data compression: Bitwise operations can be used to compress data by reducing the number of bits needed to represent it.
- Cryptography: Bitwise operations are used in some cryptographic algorithms to perform bit-level operations on binary data.
4. What is bitwise XOR?
Bitwise XOR (Exclusive Or) is a bitwise operator that compares each bit of the first number to the corresponding bit of the second number, and if the bits are different, the corresponding result bit is set to 1. If the bits are the same, the corresponding result bit is set to 0. It is represented in most programming languages by the "^" symbol.
A simple example of using the bitwise XOR operator is to toggle the value of a specific bit in a number. For example, to toggle the third bit of the number 5, which is 101 in binary, we can use the XOR operator with the number 4 (which is 100 in binary):
5 ^ 4 = 1
This results in the number 1, which has the third bit toggled.
5. What does bitwise OR do?
Bitwise OR is a bitwise operator that compares each bit of the first number to the corresponding bit of the second number, and if either of the bits is 1, the corresponding result bit is set to 1. If both bits are 0, the corresponding result bit is set to 0. It is represented in most programming languages by the "|" symbol.
A simple example of using the bitwise OR operator is to set a specific bit in a number. For example, to set the third bit of the number 5, which is 101 in binary, we can use the OR operator with the number 4 (which is 100 in binary):
5 | 4 = 5
This results in the number 5, which has the third bit set.
How to Crack Embedded Software Engineering Interviews
If you need help with your prep, join Interview Kickstart's Embedded Software Engineering Interview Course — the first-of-its-kind, domain-specific tech interview prep program designed and taught by Tier-1 Embedded Software Engineers.
IK is the gold standard in tech interview prep. Our programs include a comprehensive curriculum, unmatched teaching methods, Tier-1 instructors, and career coaching to help you nail your next tech interview.
Sign up for our FREE webinar to uplevel your career!
.png)
