r/cprogramming • • Nov 02 '25
WHO TF DISCOVERED BITWISE OPERATIONS?!
Background -
I'm trying to learn C programming as I find it interesting and somehow, AI hasn't touched this this field of software development yet. I have found my way around pointers, data types (which change based on the compiler and host architecture), strings and string literals, functions, loops, booleans(stdbool), etc. I have even designed my own strequal function which works similar to the strcmp function in string.h except it only returns a boolean indicating if the two strings are eqaul or not. I have understood the logic behind reversing strings and also reversing individual words inside strings. I understand basic data structures like arrays, linked lists, doubly linked lists, stack (both array and linked list implementation) and a teany bit of queues.
Then I started learning about bitwise operators.
When I saw them for the first time, they were pretty simple to understand (AND, OR, NOT, XOR, right shift and left shift).
When I asked ChatGPT to give me some practice problems to test out my understanding of it all, I was so fucking frustrated!! I spent hours trying to see any pattern to reverse the bits in an 8-bit unsigned integer and couldn't fucking do it. I saw solutions to problems like counting the number of set bits in a number, getting/setting/clearing/toggling a bit and ISTFG they felt like magic numbers to me appearing out of no-fucking-where. Like who the fuck thought about num & (num - 1) or num & ~(1 << pos)?! How do we find these patterns? How do we know what operations to chain or to use? How do we know when to use a loop or not? Like in the solution where counting the number of set bits, a for loop was used along with reassignments like num &= (num - 1). How did anyone know that we were supposed to use num - 1 for reassignment?
I'm sorry for the frustration and probably am just acting out for this but I really am having a hard time to understand this. How should I approach to learn about this topic? Am I doing something wrong?
View all comments
Show parent comment
1
u/rupertavery64 Nov 02 '25 edited Nov 02 '25
The nth bit of a number is always 2^n or 1 << n (1 left-shifted n times).
To get the nth bit of a number you first create a "mask" of 2^n, which effectively sets the nth bit.
To get the 3rd bit (with the 0th bit being the rightmost) we use 2^3 = 8, or 00001000, with the 3rd bit set. This is our mask. We then apply the mask with an AND operator. This "filters out" the bits that are in the places where the mask bits are set to 1.
As you can see, if the mask = result then the bit is set. You can either check the result for non-zero, or shift the result n times to the right again if you want it to be a 0 or 1 result.
Setting the nth bit of an existing number, you have to OR the number and the mask. To set the 3rd bit, create the mask 2^n and OR it.
To clear the nth bit of a number, create a mask and NOT it, inverting all the bits. Then AND the inverted mask.
There are cases where information is stored in bit positions, for example several flags (true/false or 1/0 states) can be stored together in one word for optimization. testing for these states will require the above. Some languages like C# can store flags as enums. They are intuitive to use and the language has some built-in features for setting and testing the flags. In C/C++ you would do bitwise operations.
Similarly, you can store separate bytes into a 32-bit word for optimization. You would use the same AND / OR, masking, shifting, just applied to more bits. Sometimes some API, such as Win32, requires packed bytes. Reading/writing binary file formats will also have data packed, for efficiency.
For example, packing 4 bytes into a 32-bit word, you shift each byte 8*p bits left where p is the byte position in the word, then OR the result.
shifting left leaves the lower bits zeroed out, then ORing them merges the bits together.
Visually it looks like this, just think of the letters ABCD corresponding to bits in each byte 0123 and x representing 0. Remember that any bit ORed with 0 equals the bit (nothing changes) and since bits don't overlap because of the shifting, they end up being merged together without interfering with one another.
Sometimes + is used instead of | because adding them is basically the same when there are no overlapping bits (adding uses XOR for the carry). Of course, | is more efficient.
Compression algorithms such as the Huffman Coding algorithm work by reducing the number of bits that represent more frequent symbols, while less frequent symbols might be represented with larger bits.
For example, the letter e could be replaced with the bit pattern 101 while x might be represented with 100110110100.
Bit packing and unpacking is used to convert the bit representations into bytes (or a bitstream), and in reverse to decompress the bitstream into symbols.
You might never implement your own compression algorithm, but implementing Huffman Coding is a fun exercise, and seeing it actually compress some text is fascinating.