Bit Twiddling Hacks
graphics.stanford.edu
Bit Twiddling Hacks
1–10 of 38 posts
Re: Bit Twiddling Hacks
#2These are typically seen as tricks for embedded programming. But they have (at least) another useful application.
Years ago I was messing around with SAT-based bounded model checking of C programs that I was crafting. Many of these tricks allow you to remove branches/loops from your program, which is great because you end up with a smaller SAT formula, which (usually) can be solved faster.
Re: Bit Twiddling Hacks
#3The interleaving/morton code bit hacks are great. They result in serious performance improvements if you need to compute morton codes.
Re: Bit Twiddling Hacks
#4A trick I used to get the mask of least significant set bit in a bit mask: `flag = bitmask & (-bitmask)`. Works with two's complement numbers only of course. (and modern architectures have a dedicated command for this)
Re: Bit Twiddling Hacks
#5We use bit twiddling a lot to reduce conditional jumps.
This website is a great starting point if you need to learn it. Highly recommend.
Re: Bit Twiddling Hacks
#6Another simple bit-twiddling-hack (it has a proper name which I unfortunately forgot) is SIMD without SIMD instructions by masking out the top-level bits (which are essentially the carry-flags), e.g. doing eight 7-bit additions at once:
uint64_t a = ((a0 & 0x7F) | ((a1 & 0x7F)Re: Bit Twiddling Hacks
#7I once had to count the number of set bits (the Hamming weight) for an assignment. It had to be done in under 40 bitwise ops, without loops and with constants of up to 8 bits. The naive approach took way too many ops! I was stumped until I found the linked page, in particular 'Counting bits set, in parallel'[1]. Parallelism at the bit level?! That is when I realized low level programming was completely badass.
[1]: https://graphics.stanford.edu/~seander/bithacks.html#CountBi...
Re: Bit Twiddling Hacks
#8Another simple bit-twiddling-hack (it has a proper name which I unfortunately forgot) is SIMD without SIMD instructions by masking out the top-level bits (which are essentially the carry-flags), e.g. doing eight 7-bit additions at once: uint64_t a = ((a0 & 0x7F) | ((a1 & 0x7F)
The name SWAR is sometimes used (https://en.wikipedia.org/wiki/SWAR).
Indeed, even 8-bit fields can be added in parallel, using the fact that ^ is like a + that does not produce a carry:
uint64_t signmask = 0x8080808080808080;
uint64_t sum_without_sign_bits = ((x & ~signmask) + (y & ~signmask));
uint64_t sum_of_sign_bits = (x ^ y) & signmask;
return sum_without_sign_bits ^ sum_of_sign_bits;Re: Bit Twiddling Hacks
#9At my last job interview I had to implement popcount and explain how to optimise it (amongst other things).
I was able to jot down a naïve implementation and the obvious optimisation based on a lookup tables. I only vaguely remembered the Bit Twiddling treatment of the subject but, with a bit of nudging from the interviewer, I managed to implement and explain the variant that runs in O(set bits) (“Brian Kernighan's way”). I got the job.
Now, it’s fashionable to deride this this kind of code interview as unrealistic and unhelpful. But in my first week on the job, by sheer coincidence, I had to use the function. Obviously there are existing, efficient implementations, including intrinsics. But knowing how to derive an efficient implementation certainly didn’t harm. My job has since evolved into different responsibilities but low-level algorithmic knowledge is still important. I’m not sure testing for it in job interviews is generally a good idea, and designing good job interviews is certainly a big topic. But in my particular case it happened to be a relevant, fair test of my abilities.
Re: Bit Twiddling Hacks
#10These slides on Bit Hacks are interesting too if you're looking for a more verbose presentation on some of these:
https://ocw.mit.edu/courses/electrical-engineering-and-compu...
Also, curiously enough, I was on the page in the submission after a co-worker asked yesterday if there was a cleaner way to do:
return direction === 'asc' ? value : -value;