CTF: Bitwise Operations
23 challenges — Week 4
Bitwise Operations Challenges
| 23 challenges | Week 4 | Week 4 (Operators and Expressions) - PRIMARY; Weeks 9-10 (Low-level Systems Programming) - SECONDARY |
| Comprehensive bitwise operations exercises covering bit manipulation, binary number bases, bit algorithms, and bit vectors. Covers all bitwise operators (&, | , ^, ~, «, »), bit testing/setting/clearing, masks, and algorithms for bit manipulation problems. Essential for low-level systems programming, optimization, and understanding computer architecture. |
Difficulty Breakdown
| Level | Count |
|---|---|
| Beginner | 4 |
| Intermediate | 16 |
| Advanced | 3 |
Challenges
1. Ascii To Hex1
| Difficulty: Beginner | Time: ~3 min | Type: pattern recognition |
Convert ASCII characters to hexadecimal representation. Given ASCII values for ‘0’=0x30, ‘A’=0x41, ‘a’=0x61, determine hex values for other characters.
Concepts: ASCII character encoding, hexadecimal number representation, binary-to-hex conversion, ASCII patterns (digits 0x30-0x39, uppercase 0x41-0x5A, lowercase 0x61-0x7A)
2. Binary To Hex1
| Difficulty: Beginner | Time: ~4 min | Type: number base conversion |
Convert 32-bit binary representations to hexadecimal. Given binary patterns, determine the equivalent hex value.
Concepts: binary-to-hex conversion (4 binary digits = 1 hex digit), 32-bit integer representation, hexadecimal notation, grouping bits into nibbles (4-bit groups)
3. Bit Array Puzzle
| Difficulty: Intermediate | Time: ~5 min | Type: code completion |
Clever puzzle: given a 2-element array where one element is 0 and the other is 0 or 1, modify the array so both are 0 using bitwise operations. Cannot use direct assignment of 0, if/else, or loops.
Concepts: bitwise and logical operators, array indexing with computed indices, logical NOT operator (!) for boolean conversion, constraints-based problem solving
4. Bitmask0
| Difficulty: Intermediate | Time: ~8 min | Type: match expression |
Match 8 bit vector operations to their corresponding C bitwise expressions. Tests fundamental bitmask operations: testing, setting, clearing, toggling, union, intersection, removal, and subset testing.
| Concepts: bitwise AND (&) for testing and clearing, bitwise OR ( | ) for setting and union, bitwise XOR (^) for toggling, bitwise NOT (~) for complement, bit vectors as set representations |
5. Bitmask1
| Difficulty: Intermediate | Time: ~6 min | Type: match expression |
More complex bitmask operations: testing multiple bits, working with multi-bit patterns, and common bit manipulation tasks.
Concepts: multi-bit mask creation and usage, testing multiple bits simultaneously, checking for equality of masked values, alternating bit patterns (0x55555555, 0xAAAAAAAA), byte-level operations (0xff for 8 bits)
6. Bitmask2
| Difficulty: Intermediate | Time: ~6 min | Type: match expression |
Construct useful bit masks: all ones, powers of 2, ranges of bits. Critical patterns for bitwise programming.
Concepts: creating all-ones mask using NOT: ~0, left shift («) to position bits, creating ranges of bits with subtraction, most significant bit (MSB) positioning, bit mask creation patterns
7. Bitmask3
| Difficulty: Advanced | Time: ~8 min | Type: match expression |
Identify what various bitwise expressions do: power of 2 testing, negation using two’s complement, sign detection, and clearing the lowest set bit.
Concepts: left shift for powers of 2, two’s complement negation (~x+1), arithmetic right shift for sign detection (x»31), bit clearing using x&(x-1) trick, understanding what expressions compute without executing
8. Bit Representations1
| Difficulty: Intermediate | Time: ~5 min | Type: write binary pattern |
Write 32-bit binary patterns for special integer values: -1, INT_MAX, INT_MIN, UINT_MAX. Tests understanding of two’s complement and integer limits.
Concepts: two’s complement representation, signed vs unsigned integers, integer overflow and limits, sign bit position (MSB), special values in C: -1, INT_MAX, INT_MIN, UINT_MAX
9. Bitset1
| Difficulty: Intermediate | Time: ~6 min | Type: expression evaluation |
Given helper functions bitset(num, pos) and bitclear(num, pos), evaluate expressions to predict their results. Tests understanding of how bit manipulation functions work.
Concepts: bit position indexing (0 = LSB, 31 = MSB for 32-bit), understanding bitset and bitclear operations, effect of setting/clearing sign bit on signed integers, two’s complement representation, evaluation of compound bit operations
10. Bittoggle
| Difficulty: Intermediate | Time: ~4 min | Type: write function |
Write a bittoggle function that toggles (flips) a bit at a given position using XOR. Solution uses XOR: return num ^ (1 « pos);
Concepts: XOR operator (^) for toggling bits, left shift («) for creating single-bit masks, function design for bit manipulation, understanding XOR truth table (0^1=1, 1^1=0, 1^0=1, 0^0=0)
11. Bits To Flip
| Difficulty: Intermediate | Time: ~8 min | Type: write function |
Count how many bits differ between two integers. Solution: XOR the numbers to find differing bits, then count 1-bits using the n&(n-1) trick or __builtin_popcount().
Concepts: XOR for finding differing bits, popcount / bit counting algorithms, n&(n-1) technique for clearing lowest set bit, counting 1-bits in a number, handling negative numbers in bit operations
12. Bitwise1
| Difficulty: Beginner | Time: ~6 min | Type: expression evaluation |
Evaluate bitwise expressions on unsigned char values 0xf0 and 0x55. Tests understanding of all bitwise operators in action.
| Concepts: bitwise AND (&): logical AND of each bit pair, bitwise OR ( | ): logical OR of each bit pair, bitwise XOR (^): logical XOR of each bit pair, bitwise NOT (~): complement each bit, left shift («): shift bits left, fill with 0s |
13. Cmp Bits
| Difficulty: Intermediate | Time: ~6 min | Type: compare function |
Compare the count of 1-bits between two integers. Write a function returning 1 if first int has more 1-bits, -1 if second has more, 0 if equal.
Concepts: popcount (population count): counting 1-bits, handling signed integers with bit operations, comparing bit populations without direct counting, bit manipulation for comparison operations
14. Hex To Binary1
| Difficulty: Beginner | Time: ~4 min | Type: number base conversion |
Convert hexadecimal values to 32-bit binary representation. Reverse of binary_to_hex1.
Concepts: hex-to-binary conversion (1 hex digit = 4 binary digits), grouping binary digits into nibbles, maintaining 32-bit representation with leading zeros
15. Make Set
| Difficulty: Intermediate | Time: ~5 min | Type: write function |
Create a bit vector set from an array of values (1-9). Each bit represents whether that number is in the set. Solution: iterate array, OR in (1 « value) for each element.
Concepts: bit vectors as set representation, using bits to represent membership (bit i set = element i in set), OR operation for adding elements to a set, iterating arrays and applying bitwise operations, unsigned integers for bit vectors (to avoid sign bit confusion)
16. Is Single
| Difficulty: Advanced | Time: ~8 min | Type: write function |
Sudoku-related: given 3 bit vectors (used digits in row, column, box), return true if exactly one possible digit remains. Solution: union the three sets, complement to find unused, check if power of 2 (only one digit available).
Concepts: bit vector operations (union, complement), power-of-2 testing with (n & (n-1)) == 0, set operations using bitwise operations, problem decomposition (Sudoku constraint checking)
17. Next Power Of 2
| Difficulty: Intermediate | Time: ~8 min | Type: write function |
Find the next power of 2 greater than or equal to a given number n. Solution: Check if already a power of 2 using (n & (n-1)). If not, find the MSB position and shift.
Concepts: power-of-2 testing: (n & (n-1)) == 0, finding MSB (most significant bit) position, left shift to construct powers of 2, bit manipulation for algorithm efficiency
18. Occurs Odd
| Difficulty: Intermediate | Time: ~6 min | Type: write function |
Find the element that occurs an odd number of times in an array (all others occur an even number of times). Solution: XOR all elements; XORing pairs cancels out, leaving the odd-occurrence element.
Concepts: XOR properties: x^x=0, x^0=x, XOR commutativity and associativity, practical use of bitwise operations to solve set problems, linear time, constant space algorithm
19. Occurs Once
| Difficulty: Advanced | Time: ~10 min | Type: write function |
Find the element occurring once (all others exactly 3 times). Solution: Count bits at each position modulo 3. A bit set in exactly 1 element mod 3 is 1.
Concepts: bit-by-bit counting modulo 3, generalizing XOR trick (XOR works for mod 2, this is mod 3), extracting individual bits using right shift and masking, reconstructing a number from individual bits
20. Reverse Bits
| Difficulty: Intermediate | Time: ~6 min | Type: write function |
Reverse the bits in an unsigned char (8-bit). E.g., 42 = 00101010 → 01010100 = 84. Solution: shift and rebuild.
Concepts: extracting bits using right shift and AND, building a number by shifting and ORing, bit manipulation loops, working with fixed-width data (8-bit char)
21. Swap Even Odd Bits
| Difficulty: Intermediate | Time: ~6 min | Type: write function |
| Swap alternating bit positions (bit 0 ↔ bit 1, bit 2 ↔ bit 3, etc.). Solution: (n & 0xAAAAAAAA) » 1 | (n & 0x55555555) « 1 |
Concepts: alternating bit pattern masks (0xAA…, 0x55…), extracting non-contiguous bit groups, left and right shifts for bit repositioning, combining results with OR
22. Swap Xor
| Difficulty: Intermediate | Time: ~5 min | Type: write function |
Swap two integers using only XOR, without temporary variables. Solution: *a ^= *b; *b ^= *a; *a ^= *b;
Concepts: XOR trick for swapping without temporary, XOR properties and algebra, understanding pointer dereferencing in C, practical use of bitwise operations
23. Unset Rightmost Bit
| Difficulty: Intermediate | Time: ~6 min | Type: write function |
Clear (unset) the rightmost 1-bit in a number. Solution: n & (n-1). This is used in popcount and bit manipulation algorithms.
Concepts: n & (n-1) trick for clearing rightmost 1-bit, understanding two’s complement and subtraction, bit manipulation tricks for algorithm optimization, use in popcount and bit iteration algorithms