Bitwise Operator Interview Cheat Sheet: 15 Essential Questions

Bitwise operators are a set of operators in C/C++ that can perform operations on individual bits within an integer value. It does efficient manipulation of binary bits and can be used to implement various algorithms, including bit manipulation, encryption, compression, and more. The bitwise operators include AND (&), OR (|), XOR (^), NOT (~), left shift (<<), and right shift (>>). These operators work on the underlying binary representation of an integer, allowing the programmer to perform operations on specific bits within a value.

• AND (&) operator: The OR operator performs a bitwise AND operation on two values, resulting in a value where the bit is set only if both the corresponding bits in the operands are set.
• OR (|) operator: The OR operator performs a bitwise OR operation on two values, resulting in a value where the bit is set if either of the corresponding bits in the operands are set.
• XOR (^) operator: The XOR operator performs a bitwise exclusive-OR operation on two values, resulting in a value where the bit is set if exactly one of the corresponding bits in the operands are set.
• NOT (~) operator: The NOT operator performs a bitwise NOT operation on a single value, resulting in a value where each bit is inverted, i.e. 0 becomes 1 and 1 becomes 0.

Below are possibly top 15 question asked in interview.

What is the difference between a bitwise AND and a logical AND operator in C/C++?

In a bitwise AND operation, the operator (&) is applied to each individual bit of the operands. The result of the operation is a value where the corresponding bits are set only if both the bits in the operands are set.

In a logical AND operation, the operator (&&) is used to determine whether two conditions are true. The result of the operation is a boolean value (true or false) that indicates whether both conditions are true.

Lets take an example of both in below example:

int x = 13;
int y = 19;

int z = x & y;

if (x > 10 && y > 10) {
printf("x and y both are greater than 10");
}

The expression x & y performs a bitwise AND operation and sets z to the value 1 i.e. (0b00001101 AND 0b00010011 = 0b00000001.

While, The expression x > 10 && y > 10 performs a logical AND operation and evaluates to true because both conditions (x is > 10 and y is > 10) are true.

What is the purpose of the left shift operator (<<) & right shift operator (>>)?

The purpose of the left shift operator (<<) and right shift operator (>>) in C/C++ is to shift the bits of a binary representation of an integer value to the left or to the right.

The left shift operator (<<) shifts the bits of a value to the left by a specified number of positions. This has the effect of multiplying the value by 2 raised to the power of the number of positions shifted. For example, the expression x << 2 shifts the bits of x two positions to the left, effectively multiplying x by 4.

The right shift operator (>>) shifts the bits of a value to the right by a specified number of positions. This has the effect of dividing the value by 2 raised to the power of the number of positions shifted. For example, the expression x >> 2 shifts the bits of x two positions to the right, effectively dividing x by 4.

You can read this (https://takethenotes.com/multiply-by-2/) to understand it in detail.

How can we use bitwise operators to set, clear, or toggle a particular bit in a number

Set bit: You can use the bitwise OR operator (|) to set a particular bit in a number.
Clear bit: You can use the bitwise AND operator (&) to clear a particular bit in a number
Toggle bit: You can use the bitwise XOR operator (^) to toggle a particular bit in a number

#define SET_BIT(x, n) (x = x | (1 << n))
#define CLEAR_BIT(x, n) (x = x & ~(1 << n))
#define TOGGLE_BIT(x, n) (x = x ^ (1 << n))

Using these macro we can set/clear/toggle the n^th bit of x.

How can you use bitwise operators to check if a particular bit is set or clear in a number?

We can use AND (&) operator to check if any bit is set or clear. We can use the below mentioned macros to check if the n^th bit of x is set/clear.

#define IS_BIT_SET(x, n) ((x & (1 << n)) != 0)
#define IS_BIT_CLEAR(x, n) ((x & (1 << n)) == 0)

What is the bitwise operator precedence in C/C++?

The bitwise operator precedence in C/C++ is as follows (highest to lowest):

1. Bitwise complement (~)
2. Bitwise AND (&)
3. Bitwise exclusive OR (^)
4. Bitwise inclusive OR (|)
5. Left shift (<<)
6. Right shift (>>)

It is important to note that the bitwise operators have lower precedence than the arithmetic operators, relational operators, and logical operators. Therefore, when combining bitwise operations with other types of operations, it is often necessary to use parentheses to ensure that the operations are performed in the correct order.

write a code to know if the number is exact power of 2

bool isPowerOfTwo(int n) {
  return ((n > 0) && !(n & (n-1)));
}

The function works by first checking if the number is greater than 0. This is because 0 is not a power of 2. Then, the bitwise AND of the number and its decremented value is calculated. If the result is 0, then the number is an exact power of 2, since it only has one bit set. Otherwise, the number is not an exact power of 2, since it has more than one bit set.

write a macro that returns the largest multiple of 8 that is less than or equal to a given number

Below is the table of binary representation of numbers exact divisible by 8

What is common here? Ans:- last three bits are ZERO. if any number that have any of the last three bits high then it will never be exact divisible by 8.

What should we do to make be exact divisible by 8? Ans, clear the last 3 bits. Below is the answer for this question

#define PREV_EIGHT_MULTIPLE(x) ((x) & ~0x03)

Write a macro to check if a number is even or odd using bitwise

if the 0^th bit is high then the number will always be ODD and if its 0 then it will be an even number.

#define IS_EVEN(n) (!(n & 1))
#define IS_ODD(n) (n & 1)

Determine the number of bits that are set in a number by using bitwise operator

int countBitsSet(int num) {
    int count = 0;
    while (num) {
        count += (num & 1);
        num >>= 1;
    }
    return count;
}

Use bitwise operators to implement a fast algorithm for finding the least significant set bit in a number

The best approach to finding the least significant set bit in a number is to use the bitwise AND operator & with a value that has only the least significant bit set. By ANDing the number with this value, we can isolate the least significant bit. The position of this bit can then be determined by counting the number of zero bits to the right of the least significant set bit. This algorithm can be implemented in C/C++ as follows:

int findLeastSignificantSetBit(unsigned int n) {
    int position = 1;
    while ((n & 1) == 0) {
        n = n >> 1;
        position++;
    }
    return position;
}

What are a signed shift and an unsigned shift?

Let us first understand the 2’s compliment: In a computer’s memory, integers are typically stored in binary form as a series of bits. A method for storing negative integers in binary form is by using the leftmost bit as the sign bit (with 0 representing positive and 1 representing negative numbers). This method is called 2’s compliment.

For example, consider the 8-bit binary representation of the decimal number 5: 00000101
To find the 2’s complement representation of -5, we invert all of the bits: 11111010

And then add 1: 11111011

The resulting binary number, 11111011, is the 2’s complement representation of -5.

Now coming back to signed and unsigned shift, As far as I know, there is no such concept of signed or unsigned shift operation in CC++. These operators are there in Java and other languages. Theoretically,
In a signed shift, the sign bit is preserved and shifted along with the other bits. The sign of the result is determined by the sign bit, which determines whether the value is positive or negative.

In an unsigned shift, the sign bit is not preserved and all bits are shifted to the right. In case of right shift, the result is always positive, regardless of the original sign of the value because the right shift operation will add 0 at leftmost bit.

How can you use bitwise operators to implement a fast parity checker?

A parity checker is used to determine if the number of 1s in a binary representation of a number is even or odd. Bitwise operations can be used to implement a fast parity checker in C/C++.

Here’s an example implementation of a parity checker using bitwise operations

#include <stdio.h>
#include <stdbool.h>

bool parityChecker(unsigned int x) {
    bool parity = 0;
    while (x) {
        parity ^= (x & 1);
        x >>= 1;
    }
    return parity;
}

int main() {
    unsigned int x = 17;
    
    if (parityChecker(x)) {
        printf("The number %u has odd parity\n", x);
    } else {
        printf("The number %u has even parity\n", x);
    }
    return 0;
}

In this example, the parityChecker function takes an unsigned integer x as input and calculates its parity. The function uses a loop to check each bit of the number. If the current bit is 1, the parity is XORed with 1, otherwise it remains unchanged. The function returns the final parity value.

it can also be implemented using below code

bool parityCheck(unsigned int x) {
    x ^= x >> 16;
    x ^= x >> 8;
    x ^= x >> 4;
    x ^= x >> 2;
    x ^= x >> 1;
    return x & 1;
}

Use bitwise operators to generate random numbers

Bitwise operations can be used to generate random numbers in C. For example, a simple random number generator can be implemented using bitwise operations such as XOR and shifting. Here’s an example implementation of a random number generator using bitwise operations in C:

#include <stdio.h>

unsigned int seed = 123456789; // Initial seed

unsigned int randomNumber() {
    seed = seed ^ (seed << 13);
    seed = seed ^ (seed >> 17);
    seed = seed ^ (seed << 5);
    return seed;
}

int main() {
    for (int i = 0; i < 10; i++) {
        printf("Random number: %u\n", randomNumber());
    }
    return 0;
}

The randomNumber() function generates a new random number by XORing the current seed value with a value generated by shifting and rotating the seed value.

Can we use bitwise operators to implement a simple encryption or decryption algorithm?

Yes, we can use bitwise XOR operator to implement simple excryption or decryption. IN many application XOR is used to generated the 8bit checksum of a data stream.

For example, a simple encryption algorithm can be implemented using bitwise XOR. In this algorithm, a key is XORed with the original data to produce the encrypted data. To decrypt the data, the encrypted data is XORed with the same key.

Here’s an example implementation of a simple encryption/decryption algorithm using XOR in C++:

#include <iostream>
using namespace std;

const int key = 0x55; // Key for encryption/decryption

int main() {
    unsigned char originalData = 0x42;
    cout << "Original Data: " << hex << (int)originalData << endl;

    // Encryption
    unsigned char encryptedData = originalData ^ key;
    cout << "Encrypted Data: " << hex << (int)encryptedData << endl;

    // Decryption
    unsigned char decryptedData = encryptedData ^ key;
    cout << "Decrypted Data: " << hex << (int)decryptedData << endl;

    return 0;
}

What are some real-world applications of bitwise operators

Bitwise operators have various real-world applications in computer science and engineering. Some common real-world applications of bitwise operators include:

1. Cryptography: Bitwise operations are used in cryptographic algorithms to scramble and descramble data for secure communication.
2. Image Processing: Bitwise operations are used to perform bit-level manipulations on images, such as masking, thresholding, and color space conversions.
3. Error Correction: Bitwise operations are used in error correction algorithms to detect and correct errors in data transmission.
4. Memory Management: Bitwise operations can be used to efficiently allocate and manage memory in computer systems. For example, bitwise operations can be used to set and clear specific bits in a memory address to track the status of memory blocks.
5. Networking: Bitwise operations are used in networking protocols to manipulate the header and payload of network packets.
6. Processor Design: Bitwise operations are used in the design of computer processors to perform various operations on binary data, such as shifting, rotating, and masking.

References

• Bitwise operation – Wikipedia
• https://takethenotes.com/multiply-by-2/