6.8 Bitwise Operations (C Programming)

Why This Matters

The understanding of bitwise operations is crucial in C programming for several reasons:

1. Solving Complex Problems: Bitwise operations provide a powerful tool to manipulate and test individual bits, which can be essential when dealing with complex problems that involve flags, masks, or specific bit patterns.
2. Debugging Real-World Bugs: Many bugs in C programs can be traced back to issues with bitwise operations, particularly when working with binary data structures like files, network packets, or low-level memory management.
3. Acing Coding Interviews: Knowledge of bitwise operations is often tested during coding interviews, especially for system programming and algorithmic problems that require manipulating bits directly.
4. Optimizing Performance: Bitwise operations can be faster than their logical counterparts because they operate on individual bits rather than comparing values. This can lead to performance improvements in certain scenarios.

Prerequisites

Before diving into bitwise operations, it's essential to have a good understanding of the following topics:

1. Basic C programming concepts such as variables, data types, and operators
2. Arithmetic and shift operations in C
3. Understanding binary numbers and their representation
4. Familiarity with the ASCII table is also helpful for working with character-based problems involving bitwise operations.
5. Understanding logical operators (&&, ||, !) and their precedence
6. Knowledge of C control structures like loops, conditional statements, and functions

Core Concept

Bitwise operations treat each bit of an integer independently. They are not allowed for floating-point types in C. In this section, we will explore four main bitwise operators: ~, &, |, and ^.

Bitwise NOT (~)

The ~ operator performs a bitwise complement operation on its operand. It changes each bit from 1 to 0 or from 0 to 1. For example, ~0b10101000 results in 0b11111111111111111111111101010111.

#include <stdio.h>
int main() {
int a = 0b10101000;
printf("Before: %d\n", a);
a = ~a;
printf("After: %d\n", a);
return 0;
}

Output:

Before: 2048
After: 65279

It is useful to remember that ~ x + 1 equals the negative of x, for integers, and ~ x equals the negative value of x - 1.

Bitwise AND (&)

The & operator performs a bitwise "and" or "conjunction" operation. Each bit in the result is 1 if that bit is 1 in both operands. For example, 0b10101010 & 0b11001100 results in 0b10001000.

#include <stdio.h>
int main() {
int a = 0b10101010;
int b = 0b11001100;
printf("a: %d\n", a);
printf("b: %d\n", b);
printf("a & b: %d\n", a & b);
return 0;
}

Output:

a: 4058
b: 2660
a & b: 1000

Bitwise OR (|)

The | operator performs a bitwise "or" ("inclusive or" or "disjunction") operation. Each bit in the result is 1 if that bit is 1 in either operand. For example, 0b10101010 | 0b11001100 results in 0b11101110.

#include <stdio.h>
int main() {
int a = 0b10101010;
int b = 0b11001100;
printf("a: %d\n", a);
printf("b: %d\n", b);
printf("a | b: %d\n", a | b);
return 0;
}

Output:

a: 4058
b: 2660
a | b: 4718

Bitwise XOR (^)

The ^ operator performs a bitwise "exclusive or" operation. Each bit in the result is 1 if that bit is 1 in exactly one of the operands. For example, 0b10101010 ^ 0b11001100 results in 0b01100110.

#include <stdio.h>
int main() {
int a = 0b10101010;
int b = 0b11001100;
printf("a: %d\n", a);
printf("b: %d\n", b);
printf("a ^ b: %d\n", a ^ b);
return 0;
}

Output:

a: 4058
b: 2660
a ^ b: 3718

To understand the effect of these operators on signed integers, keep in mind that all modern computers use two's-complement representation for negative integers. This means that the highest bit of the number indicates the sign; it is 1 for a negative number and 0 for a positive number. In a negative number, the value in the other bits increases as the number gets closer to zero, so that 0b111...11 is -1 and 0b100...00 is the most negative possible integer.

Worked Example

Let's consider a practical example where we use bitwise operations to manipulate a binary number. Suppose we have a 32-bit integer num that represents a combination of flags and an offset within shared memory. The bottom three bits (LOWBITS says how many) are special flags, while the remaining bits represent the offset. Here's how to get just the offset and add it to the base address:

#include <stdio.h>
int base_address = 0x12345678; // Base address of shared memory
int num = 0b11101101; // Example number with flags and offset
int LOWBITS = 3; // Number of bottom bits as flags

int get_offset(int num) {
int mask = ~(~0 << LOWBITS); // Create a mask to isolate the bottom bits
return (num & mask) >> LOWBITS; // Shift and isolate the bottom bits, then convert to an integer
}

int main() {
int offset = get_offset(num);
printf("Offset: %d\n", offset);
int address = base_address + offset;
printf("Address: %x\n", address);
return 0;
}

Output:

Offset: 14
Address: 1234568c

In this example, we create a function get_offset() that takes an integer representing flags and offset, creates a mask to isolate the bottom bits (flags), shifts them to the right, and converts them back to an integer. This allows us to extract just the offset from the given number.

Common Mistakes

1. Forgetting to shift the mask by the correct number of bits (LOWBITS in this example) before using it as a mask.
2. Not shifting the isolated bottom bits to convert them back to an integer after isolating them with the mask.
3. Assuming that bitwise operators have specific precedence over other operators, leading to incorrect results due to operator confusion or ambiguity. Always use parentheses to explicitly specify the nesting among these operators.
4. Not considering the sign of integers when using bitwise operations, especially with signed integers represented in two's complement.
5. Misunderstanding the difference between logical and bitwise operators, leading to incorrect results or bugs due to operator confusion.
6. Using bitwise operators on floating-point numbers, which are not allowed in C.
7. Not testing edge cases when using bitwise operations to ensure correctness and avoid unexpected behavior.

Practice Questions

1. Write a program to check if a number is odd using only bitwise operations.
2. Given two integers a and b, write a program that finds their greatest common divisor (GCD) using the bitwise AND operator.
3. Write a program to flip the bits of an integer, i.e., change 1s to 0s and 0s to 1s.
4. Write a program to count the number of set bits in an integer using only bitwise operations.
5. Write a program to find the first set bit (from right to left) in an integer using only bitwise operators.
6. Write a program to check if a number is a power of 2 using only bitwise operators.
7. Write a program to swap two integers without using temporary variables or any arithmetic operations.
8. Write a program to find the binary representation of an integer using only bitwise operators and loops.
9. Write a program to rotate an integer left by a given number of positions using only bitwise operators.
10. Write a program to implement a simple encryption scheme using bitwise XOR with a key.
11. Write a program to find the sum of two integers using only bitwise operations (without using arithmetic operators).
12. Write a program to check if an integer is prime using only bitwise operators.
13. Write a program to implement a simple hash function using bitwise operations and XOR.
14. Write a program to find the maximum number between two integers using only bitwise operators (without using arithmetic operators).
15. Write a program to check if an integer is palindromic using only bitwise operators.

FAQ

1. Why can't we use bitwise operators with floating-point numbers?

Bitwise operators treat each bit independently, which doesn't make sense for floating-point numbers since they are represented as a sign, exponent, and mantissa.

1. What is the difference between & (bitwise AND) and && (logical AND)?

& performs a bitwise AND operation on its operands, while && evaluates to true only if both conditions are true, and it short-circuits the evaluation if the first condition is false.

1. What is the difference between | (bitwise OR) and || (logical OR)?

| performs a bitwise OR operation on its operands, while || evaluates to true if either of the conditions is true, and it short-circuits the evaluation if the first condition is true.

1. What is the difference between ^ (bitwise XOR) and != (inequality)?

^ performs a bitwise XOR operation on its operands, while != compares the values of two variables for inequality.

1. How can we use bitwise operators to check if a number is a power of 2?

A number is a power of 2 if and only if it is equal to its binary representation without any bits set other than the least significant one (1). You can write a program that checks this condition using bitwise AND and right shift operations.

1. What are some common pitfalls or mistakes when working with bitwise operators?

Common pitfalls include forgetting to shift the mask by the correct number of bits, not shifting the isolated bottom bits to convert them back to an integer after isolating them with the mask, assuming that bitwise operators have specific precedence over other operators, and misinterpreting the results due to operator confusion or ambiguity.

1. What is the difference between a logical AND (&&) and a short-circuit logical AND (&)?

The main difference is that && evaluates its operands only if necessary, while & always performs both operations regardless of their outcome. In other words, && uses short-circuiting to optimize the evaluation process, while & does not.

1. What is the difference between a logical OR (||) and a short-circuit logical OR (|)?

The main difference is that || evaluates its operands only if necessary, while | always performs both operations regardless of their outcome. In other words, || uses short-circuiting to optimize the evaluation process, while | does not.

1. What are some practical applications of bitwise operators in C programming?

Practical applications include manipulating flags, masks, and specific bit patterns; debugging