c
exercises
exercises.c🔧c
/**
* =============================================================================
* Bit Manipulation in C - Exercises
* =============================================================================
*
* Practice exercises for bit manipulation techniques.
*
* Compile: gcc -Wall -Wextra -std=c99 -o exercises exercises.c
* Run: ./exercises
*
* =============================================================================
*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>
#include <stdint.h>
// =============================================================================
// Helper Functions (provided for your use)
// =============================================================================
void print_binary8(uint8_t value, const char *label) {
printf("%s: ", label);
for (int i = 7; i >= 0; i--) {
printf("%d", (value >> i) & 1);
if (i == 4) printf(" ");
}
printf(" (0x%02X)\n", value);
}
void print_binary32(uint32_t value, const char *label) {
printf("%s: ", label);
for (int i = 31; i >= 0; i--) {
printf("%d", (value >> i) & 1);
if (i % 8 == 0 && i > 0) printf(" ");
}
printf(" (0x%08X)\n", value);
}
// =============================================================================
// Exercise 1: Basic Bit Operations
// =============================================================================
/**
* Implement the following functions:
*
* 1. set_bit(n, pos) - Set bit at position 'pos' in 'n'
* 2. clear_bit(n, pos) - Clear bit at position 'pos' in 'n'
* 3. toggle_bit(n, pos) - Toggle bit at position 'pos' in 'n'
* 4. check_bit(n, pos) - Return true if bit at 'pos' is set
*
* Positions are 0-indexed from the right (LSB).
*/
uint32_t set_bit(uint32_t n, int pos) {
// YOUR CODE HERE
return 0;
}
uint32_t clear_bit(uint32_t n, int pos) {
// YOUR CODE HERE
return 0;
}
uint32_t toggle_bit(uint32_t n, int pos) {
// YOUR CODE HERE
return 0;
}
bool check_bit(uint32_t n, int pos) {
// YOUR CODE HERE
return false;
}
void exercise1(void) {
printf("=== Exercise 1: Basic Bit Operations ===\n");
uint32_t test = 0b10101010;
printf("Original: ");
print_binary8(test, "");
printf("set_bit(test, 0): ");
print_binary8(set_bit(test, 0), "");
printf("clear_bit(test, 3): ");
print_binary8(clear_bit(test, 3), "");
printf("toggle_bit(test, 4): ");
print_binary8(toggle_bit(test, 4), "");
printf("check_bit(test, 3): %s\n", check_bit(test, 3) ? "true" : "false");
printf("check_bit(test, 2): %s\n", check_bit(test, 2) ? "true" : "false");
printf("\n");
}
// =============================================================================
// Exercise 2: Count Set Bits
// =============================================================================
/**
* Implement a function to count the number of set bits (1s) in an integer.
*
* Hint: Use Brian Kernighan's algorithm: n & (n-1) clears the lowest set bit
*/
int count_set_bits(uint32_t n) {
// YOUR CODE HERE
return 0;
}
void exercise2(void) {
printf("=== Exercise 2: Count Set Bits ===\n");
uint32_t tests[] = {0, 1, 7, 15, 16, 255, 0xFFFFFFFF};
int expected[] = {0, 1, 3, 4, 1, 8, 32};
for (int i = 0; i < 7; i++) {
int result = count_set_bits(tests[i]);
printf("count_set_bits(0x%X) = %d (expected %d) %s\n",
tests[i], result, expected[i],
result == expected[i] ? "✓" : "✗");
}
printf("\n");
}
// =============================================================================
// Exercise 3: Power of Two
// =============================================================================
/**
* Implement functions to:
* 1. Check if a number is a power of 2
* 2. Find the next power of 2 >= n
* 3. Find the previous power of 2 <= n
*
* Hint: A power of 2 has exactly one bit set: n & (n-1) == 0
*/
bool is_power_of_two(uint32_t n) {
// YOUR CODE HERE
return false;
}
uint32_t next_power_of_two(uint32_t n) {
// YOUR CODE HERE
return 0;
}
uint32_t prev_power_of_two(uint32_t n) {
// YOUR CODE HERE
return 0;
}
void exercise3(void) {
printf("=== Exercise 3: Power of Two ===\n");
printf("is_power_of_two tests:\n");
uint32_t pow_tests[] = {0, 1, 2, 3, 4, 5, 8, 16, 17, 32, 64, 100, 128};
bool expected_pow[] = {false, true, true, false, true, false, true, true, false, true, true, false, true};
for (int i = 0; i < 13; i++) {
bool result = is_power_of_two(pow_tests[i]);
printf(" is_power_of_two(%u) = %s (expected %s) %s\n",
pow_tests[i], result ? "true" : "false",
expected_pow[i] ? "true" : "false",
result == expected_pow[i] ? "✓" : "✗");
}
printf("\nnext_power_of_two tests:\n");
uint32_t next_tests[] = {0, 1, 2, 3, 5, 7, 9, 15, 17, 100};
uint32_t expected_next[] = {1, 1, 2, 4, 8, 8, 16, 16, 32, 128};
for (int i = 0; i < 10; i++) {
uint32_t result = next_power_of_two(next_tests[i]);
printf(" next_power_of_two(%u) = %u (expected %u) %s\n",
next_tests[i], result, expected_next[i],
result == expected_next[i] ? "✓" : "✗");
}
printf("\n");
}
// =============================================================================
// Exercise 4: Bit Reversal
// =============================================================================
/**
* Implement a function to reverse the bits in a byte (8 bits).
*
* Example: 0b11001010 -> 0b01010011
*
* Hint: You can swap groups of bits progressively:
* - Swap nibbles (4 bits)
* - Swap pairs (2 bits)
* - Swap individual bits
*/
uint8_t reverse_bits_8(uint8_t n) {
// YOUR CODE HERE
return 0;
}
void exercise4(void) {
printf("=== Exercise 4: Bit Reversal ===\n");
uint8_t tests[] = {0x00, 0x01, 0x80, 0x0F, 0xF0, 0xAA, 0x55, 0xCA};
uint8_t expected[] = {0x00, 0x80, 0x01, 0xF0, 0x0F, 0x55, 0xAA, 0x53};
for (int i = 0; i < 8; i++) {
uint8_t result = reverse_bits_8(tests[i]);
printf("reverse_bits_8(0x%02X) = 0x%02X (expected 0x%02X) %s\n",
tests[i], result, expected[i],
result == expected[i] ? "✓" : "✗");
}
printf("\n");
}
// =============================================================================
// Exercise 5: Extract and Insert Bit Fields
// =============================================================================
/**
* Implement functions to:
* 1. Extract a range of bits from a value
* 2. Insert a value into a specific bit range
*
* Parameters:
* - value: The original value
* - start: Starting bit position (0-indexed from right)
* - length: Number of bits in the field
* - field: (for insert) The value to insert
*/
uint32_t extract_bits(uint32_t value, int start, int length) {
// YOUR CODE HERE
return 0;
}
uint32_t insert_bits(uint32_t value, uint32_t field, int start, int length) {
// YOUR CODE HERE
return 0;
}
void exercise5(void) {
printf("=== Exercise 5: Extract and Insert Bit Fields ===\n");
// Test extraction
printf("Extracting bits:\n");
uint32_t test_val = 0xABCD1234;
print_binary32(test_val, " Value");
printf(" extract_bits(0x%08X, 0, 4) = 0x%X (expected 0x4)\n",
test_val, extract_bits(test_val, 0, 4));
printf(" extract_bits(0x%08X, 4, 4) = 0x%X (expected 0x3)\n",
test_val, extract_bits(test_val, 4, 4));
printf(" extract_bits(0x%08X, 8, 8) = 0x%X (expected 0x12)\n",
test_val, extract_bits(test_val, 8, 8));
printf(" extract_bits(0x%08X, 16, 16) = 0x%X (expected 0xABCD)\n",
test_val, extract_bits(test_val, 16, 16));
// Test insertion
printf("\nInserting bits:\n");
printf(" insert_bits(0x00000000, 0xF, 4, 4) = 0x%08X (expected 0x000000F0)\n",
insert_bits(0x00000000, 0xF, 4, 4));
printf(" insert_bits(0xFFFFFFFF, 0x0, 8, 8) = 0x%08X (expected 0xFFFF00FF)\n",
insert_bits(0xFFFFFFFF, 0x0, 8, 8));
printf(" insert_bits(0xABCD1234, 0x99, 8, 8) = 0x%08X (expected 0xABCD9934)\n",
insert_bits(0xABCD1234, 0x99, 8, 8));
printf("\n");
}
// =============================================================================
// Exercise 6: Rotate Bits
// =============================================================================
/**
* Implement functions to rotate bits left and right for a 32-bit value.
*
* Rotation wraps bits around - bits shifted out one side come in the other.
*
* Example: rotate_left(0x80000001, 1) = 0x00000003
*/
uint32_t rotate_left(uint32_t value, int count) {
// YOUR CODE HERE
return 0;
}
uint32_t rotate_right(uint32_t value, int count) {
// YOUR CODE HERE
return 0;
}
void exercise6(void) {
printf("=== Exercise 6: Rotate Bits ===\n");
uint32_t test = 0x80000001;
printf("Testing rotation of 0x%08X:\n", test);
printf(" rotate_left(0x%08X, 1) = 0x%08X (expected 0x00000003)\n",
test, rotate_left(test, 1));
printf(" rotate_left(0x%08X, 4) = 0x%08X (expected 0x00000018)\n",
test, rotate_left(test, 4));
printf(" rotate_right(0x%08X, 1) = 0x%08X (expected 0xC0000000)\n",
test, rotate_right(test, 1));
printf(" rotate_right(0x%08X, 4) = 0x%08X (expected 0x18000000)\n",
test, rotate_right(test, 4));
// Verify rotation wraps correctly
uint32_t test2 = 0x12345678;
printf("\nVerifying full rotation of 0x%08X:\n", test2);
printf(" rotate_left(x, 32) = 0x%08X (expected 0x%08X)\n",
rotate_left(test2, 32), test2);
printf(" rotate_left(rotate_right(x, 8), 8) = 0x%08X\n",
rotate_left(rotate_right(test2, 8), 8));
printf("\n");
}
// =============================================================================
// Exercise 7: Find Unique Element
// =============================================================================
/**
* In an array where every element appears twice except one, find the unique element.
*
* Use XOR property: a ^ a = 0 and a ^ 0 = a
*
* Also implement: Find two unique elements when all others appear twice.
* Hint: XOR all elements, then use the result to partition the array.
*/
int find_single_unique(int arr[], int n) {
// YOUR CODE HERE
return 0;
}
void find_two_unique(int arr[], int n, int *a, int *b) {
// YOUR CODE HERE (set *a and *b to the two unique values)
*a = 0;
*b = 0;
}
void exercise7(void) {
printf("=== Exercise 7: Find Unique Element ===\n");
// Test single unique
int arr1[] = {2, 3, 5, 4, 5, 3, 4};
printf("Array: {2, 3, 5, 4, 5, 3, 4}\n");
printf("Single unique: %d (expected 2)\n", find_single_unique(arr1, 7));
int arr2[] = {1, 1, 2, 2, 3, 3, 99};
printf("Array: {1, 1, 2, 2, 3, 3, 99}\n");
printf("Single unique: %d (expected 99)\n", find_single_unique(arr2, 7));
// Test two unique
int arr3[] = {1, 2, 1, 3, 2, 5, 3, 7};
int a, b;
find_two_unique(arr3, 8, &a, &b);
printf("\nArray: {1, 2, 1, 3, 2, 5, 3, 7}\n");
printf("Two unique: %d and %d (expected 5 and 7)\n", a, b);
printf("\n");
}
// =============================================================================
// Exercise 8: Swap Without Temp
// =============================================================================
/**
* Implement functions to swap values without using a temporary variable.
* Use XOR for integers, but be careful about edge cases!
*
* Also implement: swap nibbles in a byte (swap upper and lower 4 bits)
*/
void swap_xor(int *a, int *b) {
// YOUR CODE HERE (be careful if a == b!)
}
uint8_t swap_nibbles(uint8_t n) {
// YOUR CODE HERE
return 0;
}
void exercise8(void) {
printf("=== Exercise 8: Swap Without Temp ===\n");
// Test XOR swap
int x = 15, y = 27;
printf("Before swap: x = %d, y = %d\n", x, y);
swap_xor(&x, &y);
printf("After swap: x = %d, y = %d\n", x, y);
// Test with same value
int z = 42;
int *pz = &z;
printf("\nSwapping same variable with itself:\n");
printf("Before: z = %d\n", z);
swap_xor(pz, pz); // This is a tricky edge case!
printf("After: z = %d (should still be 42)\n", z);
// Test nibble swap
printf("\nSwapping nibbles:\n");
uint8_t nibble_tests[] = {0x12, 0xAB, 0x00, 0xFF, 0x0F, 0xF0};
for (int i = 0; i < 6; i++) {
printf(" swap_nibbles(0x%02X) = 0x%02X\n",
nibble_tests[i], swap_nibbles(nibble_tests[i]));
}
printf("\n");
}
// =============================================================================
// Exercise 9: Bit Parity
// =============================================================================
/**
* Implement functions to:
* 1. Calculate the parity of a byte (1 if odd number of 1s, 0 if even)
* 2. Add parity bit to 7 data bits (even parity)
* 3. Check if a byte with parity is valid (even parity)
*
* Even parity: total number of 1s (including parity bit) should be even
*/
int parity8(uint8_t n) {
// YOUR CODE HERE
return 0;
}
uint8_t add_parity(uint8_t data7) {
// data7 has 7 data bits in lower 7 bits
// Add even parity bit in bit 7
// YOUR CODE HERE
return 0;
}
bool check_parity(uint8_t byte_with_parity) {
// Return true if even parity is valid
// YOUR CODE HERE
return false;
}
void exercise9(void) {
printf("=== Exercise 9: Bit Parity ===\n");
// Test parity
printf("Parity tests:\n");
uint8_t parity_tests[] = {0x00, 0x01, 0x03, 0x07, 0x0F, 0xFF};
for (int i = 0; i < 6; i++) {
printf(" parity8(0x%02X) = %d\n", parity_tests[i], parity8(parity_tests[i]));
}
// Test add parity
printf("\nAdding parity (7 data bits):\n");
uint8_t data_tests[] = {0x00, 0x01, 0x55, 0x7F};
for (int i = 0; i < 4; i++) {
uint8_t with_parity = add_parity(data_tests[i]);
printf(" add_parity(0x%02X) = 0x%02X, check_parity = %s\n",
data_tests[i], with_parity,
check_parity(with_parity) ? "valid" : "invalid");
}
// Test with error
printf("\nChecking corrupted data:\n");
uint8_t good = add_parity(0x55);
uint8_t bad = good ^ 0x10; // Flip a bit
printf(" Good data: 0x%02X, check_parity = %s\n",
good, check_parity(good) ? "valid" : "invalid");
printf(" Bad data: 0x%02X, check_parity = %s\n",
bad, check_parity(bad) ? "valid" : "invalid");
printf("\n");
}
// =============================================================================
// Exercise 10: Bitmap Implementation
// =============================================================================
/**
* Implement a simple bitmap (bit array) using an array of unsigned chars.
*
* Functions to implement:
* 1. bitmap_set(bitmap, index) - Set bit at index
* 2. bitmap_clear(bitmap, index) - Clear bit at index
* 3. bitmap_get(bitmap, index) - Get bit at index
* 4. bitmap_count(bitmap, size) - Count set bits in bitmap of given size (in bytes)
* 5. bitmap_find_first_set(bitmap, size) - Find index of first set bit (-1 if none)
* 6. bitmap_find_first_clear(bitmap, size) - Find index of first clear bit (-1 if none)
*/
void bitmap_set(uint8_t *bitmap, int index) {
// YOUR CODE HERE
}
void bitmap_clear(uint8_t *bitmap, int index) {
// YOUR CODE HERE
}
bool bitmap_get(uint8_t *bitmap, int index) {
// YOUR CODE HERE
return false;
}
int bitmap_count(uint8_t *bitmap, int size) {
// YOUR CODE HERE
return 0;
}
int bitmap_find_first_set(uint8_t *bitmap, int size) {
// YOUR CODE HERE
return -1;
}
int bitmap_find_first_clear(uint8_t *bitmap, int size) {
// YOUR CODE HERE
return -1;
}
void print_bitmap(uint8_t *bitmap, int size) {
printf("[");
for (int i = 0; i < size * 8; i++) {
printf("%d", bitmap_get(bitmap, i) ? 1 : 0);
if ((i + 1) % 8 == 0 && i < size * 8 - 1) printf(" ");
}
printf("]\n");
}
void exercise10(void) {
printf("=== Exercise 10: Bitmap Implementation ===\n");
// Create a 32-bit bitmap (4 bytes)
uint8_t bitmap[4] = {0};
int size = 4;
printf("Initial bitmap:\n ");
print_bitmap(bitmap, size);
// Set some bits
printf("\nSetting bits 0, 7, 15, 16, 31:\n ");
bitmap_set(bitmap, 0);
bitmap_set(bitmap, 7);
bitmap_set(bitmap, 15);
bitmap_set(bitmap, 16);
bitmap_set(bitmap, 31);
print_bitmap(bitmap, size);
printf(" Count of set bits: %d (expected 5)\n", bitmap_count(bitmap, size));
// Clear a bit
printf("\nClearing bit 15:\n ");
bitmap_clear(bitmap, 15);
print_bitmap(bitmap, size);
// Find operations
printf("\nFind operations:\n");
printf(" First set bit: %d (expected 0)\n", bitmap_find_first_set(bitmap, size));
printf(" First clear bit: %d (expected 1)\n", bitmap_find_first_clear(bitmap, size));
// Clear bit 0 and check again
bitmap_clear(bitmap, 0);
printf("\nAfter clearing bit 0:\n ");
print_bitmap(bitmap, size);
printf(" First set bit: %d (expected 7)\n", bitmap_find_first_set(bitmap, size));
printf(" First clear bit: %d (expected 0)\n", bitmap_find_first_clear(bitmap, size));
printf("\n");
}
// =============================================================================
// Main Function
// =============================================================================
int main(void) {
printf("============================================================\n");
printf(" BIT MANIPULATION IN C - EXERCISES \n");
printf("============================================================\n\n");
exercise1();
exercise2();
exercise3();
exercise4();
exercise5();
exercise6();
exercise7();
exercise8();
exercise9();
exercise10();
printf("============================================================\n");
printf("Complete each exercise by implementing the functions above.\n");
printf("============================================================\n");
return 0;
}
// =============================================================================
// ANSWER KEY
// =============================================================================
/*
* Below are the solutions. Try to solve the exercises yourself first!
*/
/*
// Exercise 1: Basic Bit Operations
uint32_t set_bit(uint32_t n, int pos) {
return n | (1U << pos);
}
uint32_t clear_bit(uint32_t n, int pos) {
return n & ~(1U << pos);
}
uint32_t toggle_bit(uint32_t n, int pos) {
return n ^ (1U << pos);
}
bool check_bit(uint32_t n, int pos) {
return (n >> pos) & 1;
}
// Exercise 2: Count Set Bits
int count_set_bits(uint32_t n) {
int count = 0;
while (n) {
n &= (n - 1); // Clear lowest set bit
count++;
}
return count;
}
// Exercise 3: Power of Two
bool is_power_of_two(uint32_t n) {
return n > 0 && (n & (n - 1)) == 0;
}
uint32_t next_power_of_two(uint32_t n) {
if (n == 0) return 1;
n--;
n |= n >> 1;
n |= n >> 2;
n |= n >> 4;
n |= n >> 8;
n |= n >> 16;
return n + 1;
}
uint32_t prev_power_of_two(uint32_t n) {
if (n == 0) return 0;
n |= n >> 1;
n |= n >> 2;
n |= n >> 4;
n |= n >> 8;
n |= n >> 16;
return n - (n >> 1);
}
// Exercise 4: Bit Reversal
uint8_t reverse_bits_8(uint8_t n) {
n = (n & 0xF0) >> 4 | (n & 0x0F) << 4; // Swap nibbles
n = (n & 0xCC) >> 2 | (n & 0x33) << 2; // Swap pairs
n = (n & 0xAA) >> 1 | (n & 0x55) << 1; // Swap bits
return n;
}
// Exercise 5: Extract and Insert Bit Fields
uint32_t extract_bits(uint32_t value, int start, int length) {
uint32_t mask = (1U << length) - 1;
return (value >> start) & mask;
}
uint32_t insert_bits(uint32_t value, uint32_t field, int start, int length) {
uint32_t mask = ((1U << length) - 1) << start;
return (value & ~mask) | ((field << start) & mask);
}
// Exercise 6: Rotate Bits
uint32_t rotate_left(uint32_t value, int count) {
count &= 31; // Limit to 0-31
return (value << count) | (value >> (32 - count));
}
uint32_t rotate_right(uint32_t value, int count) {
count &= 31; // Limit to 0-31
return (value >> count) | (value << (32 - count));
}
// Exercise 7: Find Unique Element
int find_single_unique(int arr[], int n) {
int result = 0;
for (int i = 0; i < n; i++) {
result ^= arr[i];
}
return result;
}
void find_two_unique(int arr[], int n, int *a, int *b) {
int xor_all = 0;
for (int i = 0; i < n; i++) {
xor_all ^= arr[i];
}
// Find any set bit in xor_all
int set_bit = xor_all & (-xor_all);
// Partition and XOR
*a = 0;
*b = 0;
for (int i = 0; i < n; i++) {
if (arr[i] & set_bit) {
*a ^= arr[i];
} else {
*b ^= arr[i];
}
}
}
// Exercise 8: Swap Without Temp
void swap_xor(int *a, int *b) {
if (a != b) { // Important: don't swap if same address!
*a ^= *b;
*b ^= *a;
*a ^= *b;
}
}
uint8_t swap_nibbles(uint8_t n) {
return (n << 4) | (n >> 4);
}
// Exercise 9: Bit Parity
int parity8(uint8_t n) {
n ^= n >> 4;
n ^= n >> 2;
n ^= n >> 1;
return n & 1;
}
uint8_t add_parity(uint8_t data7) {
data7 &= 0x7F; // Ensure only 7 bits
int parity = parity8(data7);
return data7 | (parity << 7);
}
bool check_parity(uint8_t byte_with_parity) {
return parity8(byte_with_parity) == 0;
}
// Exercise 10: Bitmap Implementation
void bitmap_set(uint8_t *bitmap, int index) {
bitmap[index / 8] |= (1 << (index % 8));
}
void bitmap_clear(uint8_t *bitmap, int index) {
bitmap[index / 8] &= ~(1 << (index % 8));
}
bool bitmap_get(uint8_t *bitmap, int index) {
return (bitmap[index / 8] >> (index % 8)) & 1;
}
int bitmap_count(uint8_t *bitmap, int size) {
int count = 0;
for (int i = 0; i < size; i++) {
uint8_t byte = bitmap[i];
while (byte) {
byte &= (byte - 1);
count++;
}
}
return count;
}
int bitmap_find_first_set(uint8_t *bitmap, int size) {
for (int i = 0; i < size * 8; i++) {
if (bitmap_get(bitmap, i)) return i;
}
return -1;
}
int bitmap_find_first_clear(uint8_t *bitmap, int size) {
for (int i = 0; i < size * 8; i++) {
if (!bitmap_get(bitmap, i)) return i;
}
return -1;
}
*/