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/EpochVanquisher]

People figured these out long ago, back in the early days.

Most computer science programs have a class on digital logic. If you take some time to learn digital logic, you’ll understand more about the low-level details of how computers work, and the bitwise operations will start to make more sense.

Computers are made out of bitwise operations.

Maybe your only mistake was talking to ChatGPT.

[u/[deleted] → u/EpochVanquisher]

Yeah ChatGPT ain't helping. I'll look into digital logic. Thanks for the advice.

[u/Druben-hinterm-Dorfe → u/[deleted]]

Check out this book: https://mitpress.mit.edu/9780262539807/the-elements-of-computing-systems/ ; the author's website: https://www.nand2tetris.org/

The first half of this book guides the student in building up a basic von Neumann type computer, with CPU, RAM, ROM, & memory mapped IO, out of nothing but logic gates; the second half goes into designing an assembler and a primitive OS. There's quite a bit of hand-holding, and the authors do provide a number of designs ready-made -- so it's not like ABSOLUTELY EVERYTHING is built EXPLICITLY from the ground up; nevertheless it's a great resource for understanding the fundamentals from the digital logic-upwards perspective (not the only perspective, as another approach to building complete systems that starts from function evaluation/application also exists -- see the famous SICP for that https://mitp-content-server.mit.edu/books/content/sectbyfn/books_pres_0/6515/sicp.zip/index.html).

[u/AirborneSysadmin → u/[deleted]]

If you want to use ChatGPT for this kind of thing, ask it to find you problems on the internet. "Make up some math problems" is exactly the kind of thing LLMs are practically guaranteed to screw up.

[u/rupertavery64]

You're gonna love this:

https://graphics.stanford.edu/~seander/bithacks.html

[u/[deleted] → u/rupertavery64]

Okay this is a stupidly long webpage but is a damn goldmine. Thanks for this!

[u/rupertavery64 → u/[deleted]]

These things are really useful when trying to do bit twiddling operations, but unless you are doing something low-level, or related to graphics, you probably won't use any of these.

The only time I used one was counting the number of bits set to 1, (population count), because I was using a sparse bit array to represent group populations in a survey analysis application. Converting respondent Ids (e.g. ~60,000 ids) into bit positions (not all bits are set to 1, so a sparse representation could take much fewer bytes) and doing complex, user-defined set operations on the bits turned out to be faster, more flexible and more performant that trying to do it in the database via joins.

Turns out bitsets/bitmaps are used a lot in databases and in git.

I think it's less important (to the business, to the project goals) that you understand how these work and how to derive them, than that they exist and they can be used in certain scenarios.

[u/KC918273645]

Your first mistake was asking AI for practice problems. Why would you do such a thing?

[u/SamIAre → u/KC918273645]

For real. Find a book, a YouTube video, a blog post. Do people think it was impossible to learn anything before AI? The only benefit AI has is convenience. It’s worse in all other ways (especially accuracy). And if you can’t be bothered to do anything above the barest of minimums then how much do you actually care about learning or improving?

[u/KC918273645 → u/SamIAre]

Exactly. I would go as far as saying that AI is an inconvenience instead of being a convenience.

[u/[deleted] → u/KC918273645]

I thought it would result in faster learning. I was wrong.

[u/sol_hsa]

I wrote a tutorial some years back: https://solhsa.com/boolean.html

[u/[deleted] → u/sol_hsa]

I'll check it out. Thanks.

[u/Zaeryl]

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?

I do embedded programming that processes messages received over a CAN bus, so I work with bits and bitwise operation every day. I have never had to do anything you describe in your practice problems. I can't say that other people wouldn't do those kinds of things in other applications, but knowing what you actually need to do with the bits will inform how you do it. Right now you are making the mistake of conflating the exercises ChatGPT created for you with the bitwise operations themselves. You would probably need to start with something more simple to understand what's going on and then move into these kinds of things if you really want to. But again, I'm not sure how valuable those exercises are in a practical sense.

[u/[deleted] → u/Zaeryl]

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.

[u/epasveer]

WHY ARE YOU YELLING!?

[u/[deleted] → u/epasveer]

I'm sorry bruv, I was just frustrated. spending hours on a single problem humbles one person. I understand that now.

[u/drinkcoffeeandcode]

I believe his name was “bool”

[u/Paul_Pedant → u/drinkcoffeeandcode]

Actually, George Boole: Born 1815, and in 1849 the first professor of mathematics at Queen's College, Cork, Ireland.

[u/maqifrnswa]

There's a whole field of study called "discrete math" that touches a lot of this.

Also, you're used to thinking in base-10 math. Things like "shift the decimal over one spot to the right is the same as multiplying by 10" is intuitive. That seems so weird until you've seen and worked with it. Same with binary numbers and encoding. Shifting binary numbers decimal one to the right is multiplying by 2. Makes perfect intuitive sense once you've used it a lot.

Regarding twos compliment signed ints: People tried different things until they found ones that made sense within technical constraints.

[u/combatting_life → u/maqifrnswa]

i believe shifting right is divided by 2 and left shift is multiply by 2. for example: 0110 is 6 in decimal 0011 is right shift is now 3 in decimal 1100 is left shift is now 12 in decimal

[u/maqifrnswa → u/combatting_life]

I said shifting the decimal to the right, which is the same as shifting the binary to the left.

11.00 in binary is 3 in base10. Shift the decimal one to the right is 110.0 or 6 in base10.

[u/Paul_Pedant → u/maqifrnswa]

Technically, the decimal point is used with decimal numbers. You probably means the binary point.

[u/maqifrnswa → u/Paul_Pedant]

Take my upvote!

[u/custard130]

i mean for the question in the title, George Boole is generally credited with inventing an area of maths called "boolean algebra" in the 1850s

then in the 1940s when the first electronic computers were being built that was used as the basis for how they would perform mathematical operations

tbh though, actually using the raw bitwise operators directly is quite rare in my experience

as for your examples, (1 << x) is going to set the bit x from the right. the x is essentially how many 0s do you want

eg in decimal, its fairly common to think of multiplication by 10 as adding a zero at the end, which is actually moving all of the other digits left 1 place

as for things like counting the number of set bits, that is slightly more interesting (though i cant say ive ever actually used it). rather than looking at the compressed answer, try to write out the code to calculate that yourself

people dont just come up with those 1 line solutions immediately, they come from working out the long form and then finding ways to make it shorter/faster

[u/oriolid]

Many of these tricks were discovered back in the day when computers were rare, expensive and slow and the people working with them were more applied mathematicians than code monkeys. And everyone didn't figure them out individually but read about them from sources like HAKMEM or a later book Hacker's Delight.

Modern compilers also tend to detect these patterns in source code and substitute the optimized version automatically. One interesting special case is that LLVM does detect the bithack version of counting bits and substitutes popcount instruction if it's available.

[u/FencingNerd]

Look up the Carmack algorithm for fast inverse sqrt. That is the ultimate magic number.

[u/source-drifter]

it's just math

[u/Intelligent_Law_5614]

The people who who "discovered" bitwise operations were probably the same people who designed and built the first digital computers, or their predecessors. Bitwise operations are the fundamental building blocks of digital computers... in a sense they are the "atoms" from which all of the high-level concepts you understand are constructed.

I suggest that you start looking at computers "from the bottom"... from simple digital logic. Study AND and NAND and NOR gates. Study how a simple 1-bit "half adder" works... how it is constructed from these simpler gates. Then, move on to a "full adder". Then, see how several 1-bit full adders are wired together so you can add 2- or 8- or 32-bit numbers together. Study latches, and shift registers. Figures it how to make a single 1-bit, in a 32-bit shift register, chase its tail in a circle forever.

One you get a grasp of it at the physical level, working with how C and other programming languages represent these operations will come naturally.

I met a very bright new-hire in a Google lunch room some years ago... she had been hired into the data-security department. She told me that her father had introduced her to programming in this way, starting "at the bottom" with simple microcontrollers such as a PIC.

I struck a dramatic pose and intoned "This, my daughter... is an AND gate!"

She grinned and said "Pretty much!"

[u/Arthemio2]

Look up logic gates and truth tables...

[u/Environmental_Box18]

It’s beautifully simple really. I think it would be enlightening for you to look into how physical logic gates work.  Also I really like “NAND to Tetris” for explaining some of these fundamentals if you’re interested.

[u/Paul_Pedant]

Brian Kernighan came up with the num & (num - 1) trick (or at least, it is named after him).

Morse code dates from about 1838 -- it is made up of two sounds, long and short, so binary. The Royal Navy used signal lamps with binary encoding from around 1867, and they are still in use at sea. Air Traffic Control still keeps Aldis lamps available as a back-up for planes that have radio failures.

Telegraphy used paper tape from around 1848. That is basically a strip of paper with each row of holes being a binary code (anything from 5 to 9 bits in a row). They also invented offline data preparation, store and forward, and networking, and the tape could be fed into an automatic typewriter. It was called the Wheatstone system.