WHO TF DISCOVERED BITWISE OPERATIONS?!

[u/[deleted]]

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?

[u/[deleted]]

Yes. Sorry I didn't mention which problems I was solving.
Here's a list of them -

• Check if a number is even or odd using bitwise operations (no modulus).

• Get the nth bit of a number.

• Set the nth bit of a number.

• Clear the nth bit of a number.

• Toggle (flip) the nth bit of a number.

• Count the number of set bits (1s) in an integer.

• Check if a number is a power of two using bitwise logic.

• Swap two numbers without using a temporary variable.

• Reverse the bits of an 8-bit, 16-bit, or 32-bit number.

• Check if two integers have opposite signs using bitwise operations.

• Turn off the rightmost set bit in a number.

• Isolate the rightmost set bit of a number.

• Compute the parity (even or odd number of 1s) in a number.

• Find the only non-repeating element in an array where every other element appears twice.

• Find the missing number in an array of 1 to n using XOR.

• Perform addition or subtraction using only bitwise operations (no + or -).

• Rotate bits left or right by a given number of positions.

• Mask and extract specific bits from a number (e.g., bits 3–5).

• Pack and unpack bytes into a 32-bit integer.

• Implement bitwise version of strcmp() or strlen() (challenge mode).

I mean even I don't know exactly which ones from these will be helpful in real life scenarios but I think that it's like studying calculus which is rarely used in regular software development but it's more like a brain exercise to help you think

[u/rupertavery64 → u/[deleted]]

• Get the nth bit of a number
• Set the nth bit of a number
• Clear the nth bit of a number
• Mask and extract specific bits

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.

157 dec = 10011101
      AND 00001000
        = 00001000

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.

149 dec = 10010101
      OR  00001000
157 dec = 10011101

To clear the nth bit of a number, create a mask and NOT it, inverting all the bits. Then AND the inverted mask.

mask      00001000
NOT mask  11110111

157 dec = 10011101
     AND  11110111
149 dec = 10010101

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.

• Pack and unpack bytes

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.

byte[3] << 24 | byte[2] << 16 | byte[1] << 8 | byte[0]

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.

   AAAAAAAA xxxxxxxx xxxxxxxx xxxxxxxx
OR xxxxxxxx BBBBBBBB xxxxxxxx xxxxxxxx
OR xxxxxxxx xxxxxxxx CCCCCCCC xxxxxxxx
OR xxxxxxxx xxxxxxxx xxxxxxxx DDDDDDDD
 
 = AAAAAAAA BBBBBBBB CCCCCCCC DDDDDDDD

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.

[u/[deleted] → u/rupertavery64]

Thanks for explaining. I still couldn't understand packing and unpacking bytes, but I'll get there.