16 ms·
Low Level Bit Hacks You Absolutely Must Know
- jnwatson 8y agoThis stuff is now second nature to me after a couple decades hacking C, but boy if it was hard to find information on this stuff as a teenager in the early 90's. It is easy to forget how much the internet, and the WWW in particular, has changed programming.
- JustSomeNobody 8y ago> It is easy to forget how much the internet, and the WWW in particular, has changed programming. It really hasn't. It's just that web programming gets all the attention. Those who write hardware controllers or do embedded use bit manipulation every day. But, really, if web devs aren't familiar with this, why not? Do they not have settings to toggle in their apps?
- lsllc 8y agoCheck out Hacker's Delight (2ed) by Henry S. Warren for more of this kind of stuff.
- throwaway2016a 8y agoI was asked #1 "Check if the integer is even or odd" in an interview once. Not worded quite that way but that was the answer they were looking for. 12 years later not a single person I have hired could correctly answer that question[1] and most of them (almost all) have been great productive software developers. So "absolutely must know" is entirely dependent on the type of software you write. [1] I don't ask it in the interview, I ask it after they are hired and have been with us a few weeks just for fun.
- justin66 8y agoThey couldn't offer an answer at all, or they offered an answer that didn't involve bitwise AND?
- craftyguy 8y agoI would think a "if (x % 2 == 1) //odd" would be within the realm of most CS applicants.
- kazinator 8y agoIf x is a signed type, and negative, are you sure the modulus is positive 1? Since ISO C99, C's division operator has been required to truncate toward zero. The % operator harmonizes with that and so it yields negative remainders south of zero. In C90, it was implementation-defined, IIRC. You really just want to test for zero/nonzero, rather than x % 2 == 1.
- craftyguy 8y agoGood point. Interestingly enough, Python seems to handle this appropriately: >>> -4%2 0 >>> -8%2 0 >>> -9%2 1
- panic 8y agoYeah, Python is one of the few languages which actually defines sane behavior for integer division and modulus rather than leaving it up to the hardware. I wish more languages would follow its example!
- triska 8y agoProlog is also like this: ?- x is -4 mod 2. X = 0. ?- X is -8 mod 2. X = 0. ?- X is -9 mod 2. X = 1. Using declarative integer arithmetic, we can even express very generally that a number X is a multiple of 2: ?- X #= 2*_. This is true iff there is any integer (indicated by an anonymous variable _) that, multiplied by 2, yields X. It works for positive and negative integers. For example: ?- -4 #= 2*_. true. ?- -9 #= 2*_. false. A very nice reference on the general topic of bitwise operations is Donald Knuth's Bitwise Tricks and Techniques in Volume 4 of The Art of Computer Programming.
- twiceaday 8y agoThe following is my go-to for bit hacks https://graphics.stanford.edu/~seander/bithacks.html https://graphics.stanford.edu/~seander/bithacks.html
- deadgrey19 8y agoYes! This and only this! The posted "bit hacks" are little more than bit level manipulations exactly as intended. The Stanford hacks are truly excellent. My favourite is: https://graphics.stanford.edu/~seander/bithacks.html#RoundUpPowerOf2Float https://graphics.stanford.edu/~seander/bithacks.html#RoundUp...
- cozzyd 8y agoThat's really clever, but extremely inefficient. Something like 1 << (sizeof x - __builtin_clz(x)) should be way faster. Edit: you obviously have to multiply by 8 to convert bytes to bits
- glangdale 8y agoBy the unwritten conventions of bit hacks folks, 'builtin_clz' is not a primitive (and elsewhere in that same document you will find a brace of different ways of doing clz/ctz). Many of these documents are old and the techniques in them older still (dating back to HAKMEM). You are definitely correct on most modern architectures which have a single operation count leading/trailing zeros that are typically no more expensive than an integer multiply. This has been latency = 3, throughput = 1 for most recent Intel arch. I think a redo assuming modern architectures is long overdue; i.e. let's work off the basis that count leading/trailing zeros, PDEP/PEXT, etc are fast and cheap and start from there. Bonus round: if you had a lot of these operations to do, then you still might be able to go faster on x86 on SSE2 or AVX2 by using this trick, as the penalty to pass a SIMD register full of integers to a floating point op or vice versa is just one cycle. This trick becomes obsolete yet again with AVX512, which introduces parallel count leading zeros.
- AstralStorm 8y ago
- askvictor 8y agoThe first one (check if an integer is odd or even) is a hack, sure. But I can't think of anywhere you'd use it in the real world over (n % 2), which almost everyone will understand much quicker what you're doing. The rest aren't hacks, they're bit manipulations, which are crucial for those who need them, and just about useless to those who don't.
- cozzyd 8y agoStrangely, clang (but not gcc 7.2) with -O0 generates different code for the two. https://godbolt.org/g/N8mTL6 https://godbolt.org/g/N8mTL6
- pkaye 8y agoTry using unsigned int. I believe they are equal only for positive numbers.
- cozzyd 8y agoPerhaps in some strange numbering system but not with two's complement... (to be clear, the return type is cast to bool).
- jerrre 8y agowhy is this strange? -O0 is no optimization at all, so it isn't strange % yields an integer division right? On -03 they compile to the same, both signed and unsigned.
- cozzyd 8y agoFor some reason gcc is still optimizing it though!
- hessart 8y agoWell, you could use it while competing in the IOCCC: https://www.ioccc.org/ https://www.ioccc.org/
- jiveturkey 8y agoi dunno. only like 2 of these are “hacks”. the rest are sooo basic. and he doesn’t even have the classic swap 2 bytes/words (3 xors).
- red_light 8y agoI'm sure many will disagree, but bitwise operators and operations should be common knowledge for programmers. Why? Because it is linked to understanding how data is stored and manipulated by computers. Computer scientists and Engineers generally understand these operators, hackers and "coders" do not. With this opinion, the title does not match the content.
- ladberg 8y agoIs this not already common knowledge? It's taught pretty extensively in one of the required lower div CS classes at my university, and it's usually in other schools' curriculums from what I've seen.
- toast0 8y agoSomewhere around half of the candidates I interview have a tough time with hexadecimal, and definitely can't do bit manipulation without help. It's kind of depressing, but I've adjusted how I ask my problem since it's not actually needed to demonstrate the skills I want to see. It doesn't take long to learn bit manipulation when it's needed, even though it seems like a foundation of computing to me.
- sannee 8y agoSo is calculus, yet apparently most CS students can't really integrate shit by the time they get to graduation...
- wink 8y agoLearned to integrate in High School, never used it again for years. Used in like 1 out of 5 Math classes at the start university. Haven't needed it for a good.. 13 years I guess? Indistinguishable from "can't really integrate shit" without some hours of relearning.
- empath75 8y agoThere are a lot of computer programmers who never went to school.
- partycoder 8y agoAlso useful to generate subsets since possible the number of subsets of a set of n elements is 2^n. for (int i = 0; i << n; i++) { ... } (won't work for a large n) Also... dividing by 2 is (n >> 1) and multiplying by 2 is (n << 1).
- enthdegree 8y agolooping in order of subset size can be done easily too: https://en.wikipedia.org/wiki/Combinatorial_number_system#Applications https://en.wikipedia.org/wiki/Combinatorial_number_system#Ap...
- glangdale 8y agoIf you like this, you should check out https://graphics.stanford.edu/~seander/bithacks.html https://graphics.stanford.edu/~seander/bithacks.html as mentioned elsewhere and also the book Hacker's Delight. I would love to see these updated for SIMD and modern architectures (which change the equation quite drastically for bit hacking with 1 uop PEXT/PDEP/LZCNT/TZCNT), but that makes for a pretty huge area.
- hinkley 8y agoYears ago I recall reading a SIGPLAN paper where someone was trying to create a programming language where they represented bitwise operations and bitfields without primitive types. For the purposes of doing bit packing and other manipulations, they treated the data as an array of booleans.
- dooglius 8y agoHardware languages such as Verilog work this way natively.
- debatem1 8y agoMaybe I'm just off in my own little world but this seems a bit table stakes. Am I out of touch?
- jacquesm 8y agoNo.
- tonyarkles 8y agoWhile I am with you and the GP, other responses in this thread make it sound like we are in fact out of touch. Or grumpy old greybeards now... Kids these days...
- jacquesm 8y agoI suspect part of this is that hardly anybody that gets into programming professionally has any experience with digital logic, whereas the two used to go hand-in-hand. But the level of this post is so low as to be next to useless, I clicked fully expecting to be amazed. The title could definitely do with an upgrade.
- sethgecko 8y agoAs a Python developer who recently wrote a pure Python ECDSA/bitcoin library, these are very helpful. However performance is not always better. For example I had this function: def point_mul(p, d): n = p q = None for i in range(256): if d & (1 << i): if q is None: q = n else: q = point_add(q, n) n = point_add(n, n) return q but when i changed the loop to this : for i in reversed(format(d, 'b')): if i == '1': I found out it performed much better.
- tonyarkles 8y agoI 100% expect you're correct in your assertion, but here's the big question: do you know why the latter is faster than the former?
- f311a 8y agoPython uses arbitrary-precision integer representation, so you don't work with bits directly.
- hfdgiutdryg 8y agoI can't imagine any use for #6 on.
- Veedrac 8y agoIt's useful when you want to find the next free slot in some contiguous store. Normally you'd use ctz, but sometimes you only want 1<<ctz. An example is n-queens, eg. https://codereview.stackexchange.com/questions/75517/n-queens-brute-force-bit-by-bit https://codereview.stackexchange.com/questions/75517/n-queen...
- jankotek 8y agoNice, but hard to read and compiler does it anyway.
- bio_end_io_t 8y agoThis assumes negatives are represented as two's-complement, but that's implementation-defined. Testing whether a negative number is even by ANDing it with 1 won't work in a system that uses one's-complement.
- tomp 8y agoWhich systems don't use two's complement?
- hal_9e3 8y agohttps://en.wikipedia.org/wiki/UNIVAC_1100/2200_series#Architecture https://en.wikipedia.org/wiki/UNIVAC_1100/2200_series#Archit... "I'm not dead yet!" https://www.unisys.com/offerings/clearpath-forward/clearpath-forward-products/clearpath-os-2200-software https://www.unisys.com/offerings/clearpath-forward/clearpath... https://en.wikipedia.org/wiki/Ones%27_complement https://en.wikipedia.org/wiki/Ones%27_complement
- jandrese 8y agoA handful of ancient legacy systems. Very few people today need to worry about their webapp being ported over to UNIVAC.
- glangdale 8y agoUnisys apparently ships some emulators of a old system that still use one's complement... much as I hesitate to ever link to any ESR material, there's a good article here: http://esr.ibiblio.org/?p=7413 http://esr.ibiblio.org/?p=7413
- lallysingh 8y agoThis is the most clickbait programming article title I've ever seen.
- jacquesm 8y agoAgreed. I've flagged it.
- accnumnplus1 8y agoHow often is this doing work that the compiler is going to do for you anyway?
- dahfizz 8y agoI'm not sure I understand the question. The first one about detecting if x is odd or even is usually what the compiler will optimize the more common (x%2) == 0 to. Other than that, these are things that you have to do yourself. You can't call compiler.setMySeventhBit(); If you need to be able to flip and check bits, you have to do it yourself.
- juliangoldsmith 8y ago>y = x & (x-1) Couldn't you also do: y = x & (~1) ? I'd think that would be slightly more efficient.
- Veedrac 8y agoNo, that unsets bit #0, not the lowest set bit in x. Aka. that brings 01101₂→01100₂ correctly, but 01100₂→01100₂ instead of 01100₂→01000₂.
- juliangoldsmith 8y agoAh, I completely misunderstood what the author was doing there.
- Silhouette 8y agoThese aren't equivalent, though. The example from the linked article turns off the least significant 1 bit in x. Your version turns off the least significant bit in x, regardless of whether it is 1 or 0. They'll give the same result if x ends in a 1 or if x=0, but not in general.
- indescions_2018 8y agoSee also: The Aggregate Magic Algorithms page http://aggregate.org/MAGIC/ http://aggregate.org/MAGIC/ For example, Population Count instructions exist. But may actually be microcoded to count one bit per cycle. Vectorizing your tallies can yield log time speedups: Faster Population Counts Using AVX2 Instructions https://arxiv.org/pdf/1611.07612.pdf https://arxiv.org/pdf/1611.07612.pdf
- jacquesm 8y agoWhat is this now, junior programming lessons? You absolutely must know these because they're dead obvious and if you're just starting out with learning programming these are some of the first things you will/should learn, right after how computers store data.
- biggerfisch 8y agoWhile yes, these are pretty simple statements, most of them only being 2-3 operations, I think you might be interested to know that not every programming curriculum even covers "how computers store data". I know a fair few programmers who came from backgrounds that either never touch the difference between an integer and float, or if they did, it was only to the point of "this one stores fractions, this one doesn't". For example, no python course for scientists is going to go on in-depth about the difference between big and small endian - it just doesn't matter when you're trying to make a simple graphical model, it's far too low level. Binary operators work and are useful in JavaScript, but how many 6 week frontend bootcamps are going to cover them? What I'm getting to here is that I don't think you can just dismiss things like this because your coding background covered them - there's some pretty clear gaps in a lot of peoples' knowledge and educating them is likely only a good thing.
- ShroudedNight 8y ago> "this one stores fractions, this one doesn't" This sounds like a fast trip to the land of direct comparisons of floating point numbers. Further info: https://randomascii.wordpress.com/2012/02/25/comparing-floating-point-numbers-2012-edition/ https://randomascii.wordpress.com/2012/02/25/comparing-float...
- kuriho 8y agoIsn't it sad that most of todays junior programming curricula favour copy+pasting 10s of main() method only "applications" over explaining data types and some basic bit twiddling?
- vvanders 8y agoHere I thought this was going to be something like finding the next power of two[1]. Like a few other posters have mentioned, this is all basic bit manipulation stuff that you'd see in any perf sensitive/memory constrained codebase. [1] https://graphics.stanford.edu/~seander/bithacks.html#RoundUpPowerOf2 https://graphics.stanford.edu/~seander/bithacks.html#RoundUp...
- pointernil 8y ago- A little off-tangent maybe, but are there other professions where this kind of once important but today less important (as some claim) knowledge exists? Is this kind of "knowledge degradation" common in other industries? - On a different note: how much of mem-space bloat can be attributed to this low-level neglect? Which of course is partly caused by modern languages / programming paradigms abstracting away this low level details for sake of higher level abstractions (which only seldom break, right ;) - honorable exception: erlang bit-level pattern matching and all the power that comes with it. Btw. did any other language/lib even try to imitate that feature?
- cowholio4 8y agoSurprised I didn’t see this one on the lists. Shifting left by n bits on a signed or unsigned binary number has the effect of multiplying it by 2^n. Shifting right by n bits on a two's complement signed binary number has the effect of dividing it by 2^n, but it always rounds down (towards negative infinity).
- filereaper 8y agoI'd recommend anyone who's into bit-level hacking to have a copy of Henry Warren's Hackers Delight [1] Many of those nifty tricks are found in production systems today. [1] https://www.amazon.ca/Hackers-Delight-2nd-Henry-Warren/dp/0321842685 https://www.amazon.ca/Hackers-Delight-2nd-Henry-Warren/dp/03...
- textmode 8y agoAmateur k user. /k3 bh01:{*-1#(2 _vs x)&1} bh02:{(|(2 _vs x))y} bh03:{n:|(2 _vs x);n[y]+:1;:[x<0;-8#|n;|n]} bh04:{n:|(2 _vs x);n[y]-:1;:[x<0;-8#|n;|n]} bh05:{n:|x;:[n[y]=1;n[y]-:1;n[y]+:1];|n} bh06:{n:-1#& x;x[n]-:1;x} bh07:{n:-1#& x;m:& 8;m[n]:+1;m} bh08:{n:(*|& x)+1;m:n _!#x;x[m]:1;x} bh09:{n:|x;m:*&0 = n;n:& 8;n[m]:1;|n} bh10:{n:|x;m:*&0 = n;n[m]:1;|n} /examples: bh01 -98 bh02[-133;5] bh03[120;2] / 120 set 2nd bit bh03[-120;6] / -120 set 6th bit bh04[127;4] / 127 unset 4th bit bh05[0 1 1 1 0 1 0 1;5] bh06[0 1 0 1 0 1 1 1] bh07[1 0 1 1 1 1 0 0] bh08[0 1 0 1 0 0 0 0] bh09[1 0 1 1 1 1 0 0] bh10[1 0 1 1 1 1 0 0] Appreciated the help last time e.g. use of dyad # (take), indexing into list via juxtaposition (bh02) and use of dyad ? (find).
- textmode 8y agobh01:{*|2 _vs x=1}
- deleted 8y ago[deleted]
- thankthunk 8y agoHow are these hack? This is standard bit masking/manipulation? Every CS student learns it and the C Programming Language has examples of it.
- 112233 8y ago> if (x & (1<<n)) { > n-th bit is set Yeah, don't get a habit to do that. Instead: if ((x >> n) & 1) if x is wider type that int or n, the result of (1<<n) may be UB, and in practice the generated code will be buggy.