Bit Manipulation in C: Bitwise Operators, Tricks, Unique Elements & Subset Generation with Code Examples

1. What is Bit Manipulation?

Bit manipulation involves using bitwise operators to perform operations directly on the binary representation of numbers. It's efficient for tasks like setting, clearing, or toggling bits, and is used to optimize algorithms in terms of time and space.

2. What are the bitwise operators in C?

3. What are common bit manipulation tricks?

4. What are the advantages of bit manipulation?

5. What are the disadvantages of bit manipulation?

6. What are the applications of bit manipulation?

7. How do bitwise operators work in C?

Example: Demonstrating common bitwise operations on numbers 5 (0101) and 3 (0011).

#include <stdio.h>

int main() {
    int a = 5, b = 3; // a = 0101, b = 0011
    printf("AND (5 & 3): %d\n", a & b); // 0001 = 1
    printf("OR (5 | 3): %d\n", a | b); // 0111 = 7
    printf("XOR (5 ^ 3): %d\n", a ^ b); // 0110 = 6
    printf("NOT (~5): %d\n", ~a); // Depends on system (e.g., -6 for 32-bit)
    printf("Left Shift (5 << 1): %d\n", a << 1); // 1010 = 10
    printf("Right Shift (5 >> 1): %d\n", a >> 1); // 0010 = 2
    return 0;
}

8. How to check if a number is a power of 2 using bit manipulation?

A number n is a power of 2 if it has exactly one bit set (e.g., 4 = 0100). Check using n & (n - 1) == 0.

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

bool isPowerOfTwo(int n) {
    if (n <= 0) return false; // Handle non-positive numbers
    return (n & (n - 1)) == 0; // True if only one bit is set
}

int main() {
    printf("Is 4 a power of 2? %d\n", isPowerOfTwo(4)); // Output: 1 (true)
    printf("Is 6 a power of 2? %d\n", isPowerOfTwo(6)); // Output: 0 (false)
    return 0;
}

9. How do you count the number of set bits (1s) in a number?

Use Brian Kernighan's algorithm: n & (n - 1) clears the lowest set bit, repeat until n becomes 0.

#include <stdio.h>

int countSetBits(int n) {
    int count = 0;
    while (n) {
        n &= (n - 1); // Clear the lowest set bit
        count++;
    }
    return count;
}

int main() {
    printf("Set bits in 9 (1001): %d\n", countSetBits(9)); // Output: 2
    return 0;
}

10. What is the Unique Elements problem?

Given an array where all elements appear an even number of times except one (or a few) elements that appear an odd number of times, find the unique element(s). Bit manipulation leverages XOR's property: a ^ a = 0 and a ^ 0 = a.

11. How does bit manipulation help find a single unique element?

XOR all elements; pairs cancel out (become 0), leaving the unique element.

#include <stdio.h>

int findUnique(int arr[], int n) {
    if (n == 0) return -1; // Handle empty array
    int result = 0;
    for (int i = 0; i < n; i++) {
        result ^= arr[i]; // XOR cancels pairs
    }
    return result;
}

int main() {
    int arr[] = {7, 3, 5, 3, 5, 7, 4};
    int n = sizeof(arr) / sizeof(arr[0]);
    printf("Unique element: %d\n", findUnique(arr, n)); // Output: 4
    return 0;
}

12. How do you find two unique elements when all others appear twice?

#include <stdio.h>

void findTwoUnique(int arr[], int n, int* x, int* y) {
    if (n < 2) {
        *x = *y = -1; // Handle invalid input
        return;
    }
    int xor_all = 0;
    for (int i = 0; i < n; i++) xor_all ^= arr[i]; // x ^ y
    int set_bit = xor_all & -xor_all; // Rightmost set bit
    *x = 0, *y = 0;
    for (int i = 0; i < n; i++) {
        if (arr[i] & set_bit) *x ^= arr[i]; // Group with bit set
        else *y ^= arr[i]; // Group with bit unset
    }
}

int main() {
    int arr[] = {2, 4, 7, 9, 2, 4};
    int n = sizeof(arr) / sizeof(arr[0]);
    int x, y;
    findTwoUnique(arr, n, &x, &y);
    printf("Two unique elements: %d %d\n", x, y); // Output: 7 9 (or 9 7)
    return 0;
}

13. What is the time complexity of finding unique elements using bit manipulation?

14. What is the Subsets problem?

Given a set of distinct elements, generate all possible subsets (e.g., for {1, 2}, subsets are {}, {1}, {2}, {1, 2}). Bit manipulation uses binary numbers to represent subset choices.

15. How does bit manipulation help generate subsets?

For a set of n elements, use numbers from 0 to 2^n - 1, where each bit represents whether an element is included (1) or not (0). Example: For {1, 2}, 00 = {}, 01 = {2}, 10 = {1}, 11 = {1, 2}.

16. Can you give an example of generating subsets using bit manipulation in C?

Example: Generating all subsets for {1, 2}.

#include <stdio.h>

void generateSubsets(int arr[], int n) {
    if (n == 0) {
        printf("{ }\n");
        return;
    }
    for (int i = 0; i < (1 << n); i++) { // 0 to 2^n - 1
        printf("{ ");
        for (int j = 0; j < n; j++) {
            if (i & (1 << j)) { // Check if j-th bit is set
                printf("%d ", arr[j]);
            }
        }
        printf("}\n");
    }
}

int main() {
    int arr[] = {1, 2};
    int n = sizeof(arr) / sizeof(arr[0]);
    printf("All subsets:\n");
    generateSubsets(arr, n); // Output: { }, { 1 }, { 2 }, { 1 2 }
    return 0;
}

17. What is the time complexity of generating subsets using bit manipulation?

18. Why use bit manipulation for subsets instead of backtracking?

19. What are other common applications of bit manipulation?

20. Can you give an example of finding a missing number using bit manipulation?

Problem: Find the missing number in an array of 0 to n.

#include <stdio.h>

int findMissing(int arr[], int n) {
    if (n == 0) return 0; // Handle edge case
    int xor_all = 0, xor_arr = 0;
    for (int i = 0; i <= n; i++) xor_all ^= i; // XOR of 0 to n
    for (int i = 0; i < n; i++) xor_arr ^= arr[i]; // XOR of array
    return xor_all ^ xor_arr; // Missing number
}

int main() {
    int arr[] = {0, 1, 3, 4};
    int n = sizeof(arr) / sizeof(arr[0]);
    printf("Missing number: %d\n", findMissing(arr, n)); // Output: 2
    return 0;
}

21. What is the time complexity of finding a missing number?