7 ms·
Demystifying bitwise operations, a gentle C tutorial
- jjgreen 4y agoThat's a nicely written piece, I wish it had been around when I was first struggling with bit-mangling.
- detrites 4y agoWhile it's based on C, a large chunk of the content is simply a great introduction to number representations in other bases such as binary and hexadecimal etc. Fundamental knowledge and very well explained, and a few insights I've not seen before.
- nomemory 4y agoThanks, I wanted to post it after it was finished and revised. I also wanted to add more sections, but somebody was faster than I expected (thanks for posting it tod!). I suppose Getting to hn will add some valuable feedback in the first place. I will probably add some more content in the coming weeks.
- tester756 4y ago>Fundamental knowledge yes? no? hard to say The number of times I've needed this knowledge during all years of formal education and then years of work would be probably around 3. Then I started working with C and close to hardware and it became something that I need everyday. It's feels like bit proficiency is only useful in some very specific domains. Thought: is HTTP foundational knowledge nowadays? after all whole world is built on it if not, when will it become?
- whateveracct 4y agoI think if you work with UUIDs, it's worth learning about bitwise stuff. So backend developers in general. It's not a day-to-day skill, but it is one I've used at just about every job in the last decade to elegantly and efficiently solve hard problems regarding idempotency and randomness.
- plugin-baby 4y agoWhen would you want to perform bitwise operations on a UUID?
- edflsafoiewq 4y agoA UUID is a bunch of bit fields packed together: the version/variant, and depending on the version, fields for the datetime, MAC address, node ID, etc. You'd use bit ops to both construct and extract the fields.
- whateveracct 4y agoSay you need 5 UUIDs derived from one (say a primary key and some set of idempotency keys). You can mask them.
- JohnFen 4y agoOr if you work directly with hardware, as I do. I use bitwise stuff constantly. Or if you're doing certain obscure kinds of highly optimized mathematical operations.
- dahfizz 4y agoIf you're a web developer and your product relies on HTTP, then HTTP is absolutely fundamental knowledge. Similarly, if you're a web developer and your language doesn't even have integers, then understanding twos compliment is probably not fundamental. That said, the people who proudly know the very least amount possible to perform their day job usually are not top performers.
- tester756 4y agoOver years I've found that "top performer" is not purely about skill, often it is *just* about motivation, desire to move stuff ahead, to get things done, to improve current state of affair. Like, rarely stuff is so hard that it requires some outstanding skills.
- sumtechguy 4y agoLike you say it really depends on what your job is. For me those bit algo's for a few years were my jam. I was moving data between 4 different CPU types and across 3 different network transports depending on the project and 4 different OS's. You need to know your bits when moving data between diff arch types and across different transport layers. These days most of that same sort of thing I did then? I would drop it into a json text stream and call it a day.
- JohnFen 4y agoI think it's fundamental because understanding it goes hand-in-hand with understanding how computers actually work. When I interview applicants, I usually ask one or two questions about bitwise operations for this reason -- an engineer who knows how machines work at a very low level is valuable even if their work is not low level.
- Dowwie 4y agoSome very interesting advent of code contributions written in Rust, available on github, use bitwise operations. Shout out to Tim Visee! https://github.com/timvisee/advent-of-code-2021/blob/master/day04b/src/main.rs#L32 https://github.com/timvisee/advent-of-code-2021/blob/master/...
- philiplu 4y agoI suppose the online list of hacks at the 1st reference in the OP [1] makes more sense, but I've got a fondness for the book "Hacker's Delight", which I've owned and browsed for many years now [2]. And checking on that, I see there was a 2nd edition issued 10 years ago. Hmm, might need to pick that up. [1] https://graphics.stanford.edu/~seander/bithacks.html https://graphics.stanford.edu/~seander/bithacks.html [2] https://en.wikipedia.org/wiki/Hacker's_Delight https://en.wikipedia.org/wiki/Hacker's_Delight
- _a_a_a_ 4y agoThere are quite a lot of bit hacks on the web, but Hackers Delight is where it took off for me.It was a massive eye-opener, what was possible and even better doing it the old-fashioned way. The second book is very, very heavy on division and as such it's not really as much 'fun' as the original, however I'd still recommend it! I shared the original Hackers delight with a work colleague, who had a mathematical bent and he contacted Henry Warren with a possible addition for the forthcoming second edition, Morton curves (https://en.wikipedia.org/wiki/Z-order_curve https://en.wikipedia.org/wiki/Z-order_curve) which are extremely simple to calculate, much more so than the space filling curve given in Hackers Delight, but which despite the author's interested response to us, did not go into the second edition. My colleague was very disappointed. Me too. Morton curves are just interlace-the-bits so would have slotted in so well. Sadly there won't be a third edition as the author died.I found out when I contacted him to let him know his website was down (again!). His family let me know he had gone.
- radicalbyte 4y agoI have the second edition, back around 2010 I made a bit of a splurge on books. Super handy when you need it; which in my case has only been one time. Don't spend much time on low-level code nowadays.
- morelisp 4y agoThe last time I reached for Hacker's Delight for "productive" use it was specifically for this chapter (I was aware of space-filling curves from some years in the games industry but had never implemented one), and I remember being disappointed at the lack of depth and options compared to the rest of the book.
- calvinmorrison 4y agoFor many years I have recommended "Code" by Charles Petzold and published by microsoft. It's a great bathroom reader, reading on a road trip, or over a spaghetti dinner. It covers bottom up how computers work, starting out with - well what the heck are numbers and works up from there.
- mannyv 4y agoI thought this was going to be ridiculous but it's actually a really good. It's clear enough that you could extend it down to showing how logic gates work. The only thing missing is a little endian discussion; it assumes big endian (network byte order), and that may be confusing for all those x86 users out there.
- riceart 4y ago> that may be confusing for all those x86 users out there. It’s pretty much every user these days - even most MIPS based network oriented devices run LE. BE lost many years ago.
- mannyv 4y agoThe Network is big-endian (network byte order).
- edflsafoiewq 4y agoThat's just a data serialization format, there are zillions of those. The important thing is the endianness of the CPU.
- riceart 4y agoYou are the one that brought up CPU architectures. Except for the now aging S390/z that will probably last in a few installations forever and the 5 people that pay to run POWER workstations the world is little endian.
- nwallin 4y agoEndianness isn't relevant to any of the stuff discussed in the article. It is equally applicable to both big endian and little endian architectures.
- sebastianconcpt 4y agoArticles like these seen today should make us value more the love and effort that requires to train people. Because there is no shortage of "love" and effort (and money) for training AI models.
- cactusplant7374 4y agoI don’t understand why bit masking and manipulation is so popular when it makes the code impossible to read. I like using Ruby, string, and pack and unpack.
- dahart 4y agoWell one reason is that bit operations are significantly faster than other methods, it’s one reason for example, why compilers will turn a divide by a constant into bit manipulation. Using a scripting language’s string packing is hundreds of times slower than doing a couple of bit operations, and if there’s a memory allocation involved, it can be thousands of times slower. If you’re curious about this, I recommend doing some profiling to find out how fast your favorite algorithms are when using C bitwise operators compared to Ruby string packing. FWIW, having the code be readable is mostly a familiarity problem that you can resolve by practicing more bitwise operations, if you want. If you spend your days in Ruby, then there might not be strong reasons to, but if you’re curious and want to improve, you might have fun playing in C or C++. I spend my days mostly in CUDA, and using bit manipulation is par for the course, failure to use the best tricks can result in much lower compute throughput and much higher power consumption.
- klyrs 4y agoDo you ever wonder how Ruby's pack and unpack are implemented? https://github.com/ruby/ruby/blob/4ce642620f10ae18171b41e166aaad3944ef482a/bignum.c https://github.com/ruby/ruby/blob/4ce642620f10ae18171b41e166...
- flohofwoe 4y agoC23 finally introduces binary literals, e.g. you can write now "0b11110000" instead of "0xf0" for situations where binaries are more readable (but with a bit of 'training', hexadecimal works just as well). Also, bitwise operations are essentially "SIMD for bits" and important down on the machine code level, it makes a lot of sense to have that same functionality also in higher level languages (unfortunately not all common bitwise instructions - like rotations - made it into high level languages). (edited)
- anthomtb 4y ago
- sylware 4y agointeger promotion yuminess...
- Someone 4y agoFTA: “Based on the above picture, another important observation is that to represent the number 1078 in binary, we need at least ten memory cells (bits) for it (look at the most significant power of 2 used, which is 10)” As the picture shows, we need 11 bits, with powers ranging from zero to ten, both included (under the implicit assumption that we want to represent all integers between 0 and 1078. If all we want to represent is 1078, we can do with one or, pedantically, zero bits)
- jalino23 4y agoI wish I have a use case for this as a web dev. I just haven’t found the need for this so Ill just forget this again
- JohnFen 4y agoSounds like you need a hobby project to exercise those new muscles.
- amenghra 4y agoA related puzzle: https://www.quaxio.com/know_your_bits/ https://www.quaxio.com/know_your_bits/ More such puzzles: http://www.cs.cmu.edu/afs/cs/academic/class/15213-f02/www/L1.html http://www.cs.cmu.edu/afs/cs/academic/class/15213-f02/www/L1... and http://csapp.cs.cmu.edu/public/datalab.pdf http://csapp.cs.cmu.edu/public/datalab.pdf Bit Twiddling Hacks: http://graphics.stanford.edu/~seander/bithacks.html http://graphics.stanford.edu/~seander/bithacks.html
- flyingcircus3 4y agoFor the first puzzle, code that determines if a value has one bit high, without any if/while/for, here's what I got: !(x & (x-1)) && x Was there a "best" solution somewhere? I couldnt get the code window to work.
- amenghra 4y ago-1 is not an allowed operator in my puzzle.
- whb07 4y agoI’ve found significant code in c/c++ where bitwise operations are done for things like division etc by shifting a certain way. I Can imagine in the past, this was “faster”, yet clang/gcc can emit the same by just writing a basic A/B function. Seems the win goes to readability by reducing some of these old school hacks. What say you, greybeards ?
- AlotOfReading 4y agoI only have a little grey in my beard so far, but like all optimizations it heavily depends on context. My broad rule of thumb is that if you only care what the code does, you should let the compiler figure it out. If you care how the compiler accomplishes that goal, you should specify that rather than hoping things don't silently break in the future. This is a fairly common thing in crypto and systems code. But yes, fast inverse sqrt is obsolete.
- dhosek 4y agoOh definitely. Some of this goes back to my 6502 assembly days when there was no hardware multiply instruction. So to multiply by 40, for example. I would shift right 3 bits, store the result, shift right 2 more bits and add the stored result. Similarly, a fast divisibility test (we’ll assume we’re dividing n by some odd prime p): 1. Shift the bits of p right so that there is a 1 in the last position. 2. If n = p then p∣n, if n < p then p∤n, otherwise continue. 3. Subtract p and go back to step 1. (One of my ADD habits during meetings is to find the prime factors phone numbers or anything else very long. I do something similar with the numbers in decimal, but for this, I’ll subtract multiples of the potential divisor to get 0s at the end of the number in decimal. I remember co-workers puzzling over a piece of paper with my notes I left behind in a conference room trying to figure out what the numbers represented and how the process worked.)
- unwind 4y agoLeft, you would (obviously, this is a typo) shift left. And 3 followed by 2 since 1<<3 is 8, and 1<<5 is 32 and 8+32 is 40.
- cornstalks 4y ago
- alain94040 4y agoThis long article is a great example of why I believe GPT has a strong future. The article spends several pages to explain hexadecimal, bases, etc. Probably some fraction of the audience already knows that. In that case, the article should automatically adapt and skip that section. Some people will react negatively to the mathematical formulation, preferring the intuitive section that follows instead. But this is a static blog post, so it doesn't know how to adapt. Imagine the same post, but with some toggles/sliders (you can come up with even more sophisticated mechanisms): I indicate my level of competency, and the article re-writes itself to match my knowledge. Skip the boring math, show a lot of examples, etc. Or the opposite. The point is that it adapts to you. GPT (or some future variant) is really good at doing this.
- antegamisou 4y ago> Some people will react negatively to the mathematical formulation, preferring the intuitive section that follows instead. They have no place in software engineering then.
- nicoburns 4y agoThe problem with GPT is there’s a good chance that it introduces information which is plain wrong while doing that transformation.
- cinntaile 4y ago"Hey chatGPT, paraphrase my comment without the passive aggressive dismissal of its contents." In all seriousness though, this blogpost does exactly what it intends to do. Demistify bitwise operations and you can't skip the math.
- ablob 4y agoSure, let's just skip on the minor details that modern computation rests on. Who needed that anyway. Although I do agree that repeating the basics on every post is cumbersome, it seems adequate for this post.
- Jtsummers 4y agoGPT isn't needed. Just hyperlinks, like exist at the top of the document. Paired with the ability to expand sections either in place or in an adjacent view. State the prerequisite knowledge, then give a way to skip past the explanations or have the explanations hidden by default. Permit further expansions up to the limit of what the author cares to provide, can be added to later.
- CodeMage 4y agoHeads up: the gray_code function does not return the results shown in the table of correspondence above it. I suspect that this is because both the table and the code used were sourced from Wikipedia, and they correspond to different Gray codes. The table is for the BRGC, but the implementation isn't.
- zh3 4y agoFunnily enough just spent a day tracking down a weird problem in an embedded system - some event timestamps were getting corrupted in a weird way. The pattern wasn't obvious until in desperation I dumped them in hex and found the second MSB was toggling between 0 and 1 (whereas it should have been been part of a count sequence). That told me exactly where to look - where the count was re-assembled from four bytes and I found this upstream (paraphrased):- uint8_t tx_data[64]; .... tx_data[43] = utime>>24; tx_data[44] = utime>16; tx_data[45] = utime>>8; tx_data[46] = utime;
- zoomablemind 4y agotx_data[44] = utime>16; Good catch! I wonder if this would have been flagged with -Wall?
- edflsafoiewq 4y agoNope. There's no warning for bool->int conversion: https://stackoverflow.com/questions/28716391/gcc-forbid-implicit-bool-int-conversion https://stackoverflow.com/questions/28716391/gcc-forbid-impl...
- HarHarVeryFunny 4y agoSomewhat oddly even in C++, where bool is a distinct type, g++ doesn't have any warning for implicit bool to int conversion, although clang's clang-tidy "linter" tool does.
- zh3 4y agoNope, code was clean with -Wall on arm-9 compiler (i.e. gcc). Interesting thought now you say that (no warning) - only found it because of seeing the pattern (apropos the article) and from that having a good idea what was causing it (knowing the int was assembled a byte at a time). If I had a criticism of modern compilers, it's the blizzard of uninteresting warnings ("strncmp takes const char star, did you really mean to pass it unsigned char star") that make people want to not use -Wall.
- wg0 4y agoI'm trying to find some good resources or some book that covers modern C. For everything else from Python to Golangz Rust and everything in between - there are tons of quality books and even their own documentation in some cases is pretty decent. But not so with C. If you read this and have something, please share. Just C (not much interested in C++)
- gdprrrr 4y agohttps://www.youtube.com/watch?v=QpAhX-gsHMs https://www.youtube.com/watch?v=QpAhX-gsHMs
- rramadass 4y agoNice!
- PeterWhittaker 4y agohttps://en.cppreference.com/w/c https://en.cppreference.com/w/c
- rramadass 4y agoJust do a search on HN itself for "Modern C" and you will find a lot of discussions and recommendations. That said, you can get started with any C book (The K&R Ansi C book is a good one to start with) since it is not a "huge" language and you can get to "newer" features incrementally.
- layer8 4y agoBitwise NOT (~) gives you a bijection between negative and nonnegative integers in two’s complement representation (which negation doesn’t). This is for example exploited by the return value of Java’s binarySearch() function, which returns the (nonnegative) index of the search key when found, or else the (negative) bitwise NOT of the index where the key would have to be inserted [0]. In other words, it combines a nonnegative int value plus a flag into one int, while making the flag easily testable (< 0) and the value easily flippable (~). Strangely, the API doc doesn’t mention bitwise NOT, but instead expresses it as numeric negation minus one (which is equivalent, as TFA explains). [0] As opposed to C’s bsearch(), which only returns a position when the key was found.
- justincredible 4y ago[dead]
- tapatio 4y agoThe graphics are impressive. Specifically, I've never seen someone fold a "bit surface" in half like that. I've also never seen a ladder view. Assuming Andrei Ciobanu himself posted this, how did you come up with those views? Bored on a Friday night?
- nomemory 4y agoI am not sure if this is all that original, I am sure what other have seen that before. For me it clicked when I was redoing the graphics. What it's more interesting is that symmetry is specific to numbers in general, and the way we represent them. As an exercise if you use base 3, and plot more numbers you will also see hidden patterns. Thanks for noticing that section.
- 3pm 4y agoGreat article. One potential improvement is not to call Two's complement MSB a 'sign bit'. It implies that it only stores a sign which is how 'Signed magnitude' works. With all its downsides like having two representations for 0 etc. The beauty of Two's complement is that everything works exactly like unsigned representation, with the exception of MSB. In Two's complement MSB contributes either 0 or negative 2^N-1. So for 8 bit signed numbers, most significant bit contributes either 0 or -128. Everything else, subtraction, hardware adders etc work the same. Signed numbers are basically numbers with a flexible number line, and the first bit represents where this number line starts. I personally remember MSB for signed integers as 'origin bit'.
- dchapp 4y agoI see several people sharing the Stanford bithacks link, so I'll throw in a slightly-less well-known resource that I found particularly instructive. Basically, a collection of the lemmata we can prove about fixed-length sequences of bits and the fun algorithms that can be built atop those results. https://www.jjj.de/fxt/ https://www.jjj.de/fxt/ And for the non-pdf-phobic: https://www.jjj.de/fxt/fxtbook.pdf https://www.jjj.de/fxt/fxtbook.pdf
- olliej 4y agoI just do not understand why this document is so large - there just is not enough complexity in bitwise operators to warrant this giant multi chapter document. If anything I feel it will be confusing because it’s so much text being used to describe so little actual logic.
- hahamaster 4y agoI totally intuitively understand bitwise operators in C because I grew up with assembler and all this was my second nature. I’m afraid this article is unnecessarily complicated. The things that are eventually illuminated are really trivially simple, it’s just that they are explained in a complicated way.
- wruza 4y agoThe bitwise XOR operator (^) is a binary operator that compares the corresponding bits of two operands and returns a new value where each bit is set to 1 if the corresponding bits of the operand are different, and 0 if they are the same. You may also think about XOR in a following way: Any “1” in B flips (inverts) the corresponding bit in A. It’s like a vectorized NOT operation for single bits. Also works the other way (xor is commutative, A^B === B^A). This way of thinking is helpful when you see expressions like: X ^ (1 << 3) X ^ 8 X ^ 0b1000 Which means “X with bit 3 flipped”. (3 means 4th from the right, as in …3210).
- mtlmtlmtlmtl 4y agoXor is also equivalent to adding without propagating the carry. Ob010 + 0b011 = 0b101 (carry is propagated to the 3rd bit) 0b010 ^ 0b011 = 0b001 (same result with no carry)
- winstonprivacy 4y agoThis is great. However, he omitted one I encountered a need for pretty recently and have so far not found a good solution: How do you count the number of bits which have been set in a bitfield of type uint32_t? I couldn't find any x64_64 intrinsics for this, which would probably be incredibly efficient.
- bluesnowmonkey 4y agopopcount?
- philiplu 4y agoLike bluesnowmonkey says, the concept you're looking for is called popcount, for population count. It's also called the Hamming weight. Wikipedia has 5 different example implementations under that latter name. Many C/C++ compilers have it available as an intrinsic as well, like __builtin_popcount or __popcnt. It's also std::popcount in C++20.
- winstonprivacy 4y agoWow! Just 5 instructions. This is almost 4 times faster than my previous best solution: // 19 instructions, does not use intrinsics int countbits(unsigned x) { unsigned n; n = (x >> 1) & 0x77777777; x = x - n; n = (n >> 1) & 0x77777777; x = x - n; n = (n >> 1) & 0x77777777; x = x - n; x = (x + (x >> 4)) & 0x0F0F0F0F; x = x\*0x01010101; return x >> 24; } Amazing tip, thanks.