Demystifying bitwise operations, a gentle C tutorial
andreinc.net
andreinc.net
[1] https://graphics.stanford.edu/~seander/bithacks.html [2] https://en.wikipedia.org/wiki/Hacker's_Delight
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) 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.
What do you mean by this? Did they merely add a ton of information on division? Or did they take out the 'fun' bits from the original and replace them with division stuff?
uint8_t tx_data[64];
....
tx_data[43] = utime>>24;
tx_data[44] = utime>16;
tx_data[45] = utime>>8;
tx_data[46] = utime; tx_data[43] = utime >> 24;
tx_data[44] = utime >> 16;
tx_data[45] = utime >> 8;
tx_data[46] = utime >> 0;
tx_data[43] = utime >> (3 * 8);
tx_data[44] = utime >> (2 * 8);
tx_data[45] = utime >> (1 * 8);
tx_data[46] = utime >> (0 * 8);Having spent a lot of time digging into C code and doing microcontroller programming professionally, I have learned a certain disdain for the practice of using minimal whitespace in expressions, and the related practice of minimising LOC using C's very dense expressions syntax(unary dec/inc operators, the fact that assignment is itself an expression, etc).
The dense expressions syntax is pretty much a holdover from the time C was invented by Dennis Ritchie for the purpose of porting Unix; when it had to be typed on a painfully slow electromechanical teletype. This is also why most Unix commands are 2-4 characters long.
But it serves very little meaningful purpose today. It's important to remember that you might be able to turn 3 lines of code into 1, but it'll still be the same amount of machine code. And it will probably be harder to read, harder to change, and harder to reason about. And it can be a lot easier to miss some edgecase or even a typo like in this case. I have seen such a silly amount of off-by-one errors in C code due to some subtle misuse of unary increment/decrement that I stopped using those operators altogether. They don't improve your software in any meaningful way.
x << (3 * 8);
x << 030; tx_data[44] = utime>16;
I wonder if this would have been flagged with -Wall?
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.
> ("strncmp takes const char star, did you really mean to pass it unsigned char star")
This warning (with a different function) actually saved my bacon once, pointing me to a very obscure bug in the code.
My practice is to use -Wall and make sure that the code compiles without any warnings at all. Then I don't have a deluge of warnings to wade through.
I recommend asan too, where possible.
Why C's implicit conversions are trash. Why big endian is trash. Why you should do a reverse copy instead of stuff like this.
I will probably add some more content in the coming weeks.
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?
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.
Like, rarely stuff is so hard that it requires some outstanding skills.
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.
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 ?
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.)
For example, see the article and discussion on Bitwise Division from two days ago: https://news.ycombinator.com/item?id=34981027
Of course that tiny bit of extra work is usually negligible, but might explain why the idiom has stuck around longer than you might otherwise expect.
But yes, fast inverse sqrt is obsolete.
Makes me wonder who pays attention to this sort of thing these days :)
Usually, it can't -- but sometimes...
Oh, yes. I used to do that sort of thing frequently because the time savings was significant enough. As you say, though, compilers have improved a great deal since then, so it's not generally needed anymore.
If stupid bit tricks like that aren't necessary, they shouldn't be used. They do bring a readability/mental load cost with them.
With -O1 it performed the optimisation.
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.
And for the non-pdf-phobic: https://www.jjj.de/fxt/fxtbook.pdf
More such puzzles: http://www.cs.cmu.edu/afs/cs/academic/class/15213-f02/www/L1... and http://csapp.cs.cmu.edu/public/datalab.pdf
Bit Twiddling Hacks: http://graphics.stanford.edu/~seander/bithacks.html
!(x & (x-1)) && x
Was there a "best" solution somewhere? I couldnt get the code window to work.
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
Ob010 + 0b011 = 0b101 (carry is propagated to the 3rd bit)
0b010 ^ 0b011 = 0b001 (same result with no carry)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++)
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.
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.
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.
It’s pretty much every user these days - even most MIPS based network oriented devices run LE. BE lost many years ago.
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)
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.
// 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;
}
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.
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.
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)
https://github.com/ruby/ruby/blob/4ce642620f10ae18171b41e166...
Packing and unpacking are just some of the things you can do with bitwise operations. They are a common problem, and they are often tricky, so having an API for that makes a lot of sense. But if what you need to do is not packing and unpacking, I find it harder to understand the unpack -> string manipulation -> pack workflow than bitwise operations, it also tends to be more verbose and slower.
I agree that bit masking and manipulation is hard to read and can be misused by ego-driven programmers. But the "popularity" because because bit masking and manipulation are both fundamental to computer science and an absolute necessity in certain situations.
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.
In all seriousness though, this blogpost does exactly what it intends to do. Demistify bitwise operations and you can't skip the math.
Although I do agree that repeating the basics on every post is cumbersome, it seems adequate for this post.
They have no place in software engineering then.