6 ms·
Low Level Bit Hacks You Absolutely Must Know
- Keyframe 17y agoyou can also print binary in python like so: >>>print bin(12) 0b1100 >>>
- pkrumins 17y agoOnly Python 2.6 I think, and it does not print negatives very nicely (it prints bin(-x) = -bin(x), instead of some number representation).
- Keyframe 17y agoyes, you are right python >2.6 only
- tetha 17y agoThe best tool I know to do such things is i (debian package iprint): tetha@dev-server:~$ i 12 12 0xC 014 0b1100 '\f'
- bkudria 17y agoAKA "how to write line noise".
- pkrumins 17y agoNot quite! These are embedded programmer tools of trade. For example, you don't want to loop over bits to count number of bits in it (not covered in this article, but will be in the next part of the article). It can be done with several shifts and ANDs! Huge speedups! Another example, finding the lowest order 1-bit in a 64bit integer - it can take up to 64 iterations to find it with a loop. Instead it takes one AND and one but inversion operation (= 2 ops total)! 32x speedup!
- bcl 17y agoAbsolutely! Some of the examples, depending on the core architecture, could benefit from a table lookup, but all are good tools to have in the box.
- pkrumins 17y agoExactly! And you can get these questions even in job interviews. If you want to score the intervieews, then you better know the quick ways!
- ramchip 17y agoI like bit twiddling, but I'm not sure I'd take the job if a primary concern of the interviewer is whether I know the quick way to find the lowest-order bit in a 64-bit int...
- swolchok 17y agoThe problem is that learning to think this way in general makes you habitually write things like x >> 8 instead of x / 256, which makes your code hard to read for no benefit if you're using a compiler that was written sometime in, oh, the past 20 years. EDIT: sometimes x >> 8 is clearer, if you're actually dealing with packing bits into words, but I've just recently seen it done when the code really "meant" division.
- kqr2 17y agoAlso, even if you don't use them, it's nice to be able to read through code and understand these "idioms".
- ajross 17y agoIf you read the article instead of sneering at it, you might find it less noisy. It's an idiom. All idioms involve some learning, and generally some odd, seemingly-misapplied abstractions. But they generally have value, too, which is why they persist. In this case, the bit tricks work to map a very common metaphor in the design domain (a set of boolean flags) to a very common low-level implementation choice (the machine word). Does your application benefit from that kind of mapping? Probably not, if it's a web 2.0 thing. But don't pretend that this sort of thing is never useful either. Somewhere down in the layers you don't understand, there is real machine code running your computer. And that code, like yours, needs compact and simple storage of booleans.
- bkudria 17y agoYou're right - my comment was intentionally snarky, and deserved all the downvotes it got. You're right - these are idioms. Idioms for working with current hardware. Essentially, these are machine implementation details, and while, yes, we currently have to program machines to get anything done, not everyone finds that kind of work rewarding or interesting. I didn't mean to degrade the type of person that finds this interesting, I wanted to point out the divide between the hardware hacker and the, for a lack of a better term, math hacker. I hope that clears up my intentions!
- GeneralMaximus 17y agoThis stuff is actually pretty useful. I was recently looking at some C code that takes some text and converts it to Base64 encoding for sending it over an HTTP POST request. There was one function in my code that was, IIRC, about 30 lines long and completely unreadable. Later on, I found some code on SourceForge that did the same thing in 3 lines of bit shift operations. Here is the code in question: http://base64.sourceforge.net/b64.c http://base64.sourceforge.net/b64.c I guess I've just been spoiled by Python to not care :p
- old-gregg 17y agoFor those who enjoy these kind of problems I highly recommend "Hacker's delight". http://www.amazon.com/Hackers-Delight-Henry-S-Warren/dp/0201914654 http://www.amazon.com/Hackers-Delight-Henry-S-Warren/dp/0201...
- pkrumins 17y agoSeconded. That is an amazing book. I also recommend this much more complete article on bit hacks: http://graphics.stanford.edu/~seander/bithacks.html http://graphics.stanford.edu/~seander/bithacks.html
- gamache 17y agoAlso see the more advanced Bit Twiddling Hacks page: http://graphics.stanford.edu/~seander/bithacks.html http://graphics.stanford.edu/~seander/bithacks.html
- Confusion 17y agoI think it's unfortunate that the article does not provide real examples where these bit hacks are used. Why would I want to be able to unset the left-most 1 bit of a series of bits?
- scott_s 17y agoTwo cases are when talking to devices which use bits in a register to control behavior, and when the size of your data structure must be as compact as possible: http://miller.cs.wm.edu/lxr3.linux/http/ident?v=2.6.11.12;i=find_first_bit http://miller.cs.wm.edu/lxr3.linux/http/ident?v=2.6.11.12;i=...
- pkrumins 17y agoThanks, that's a good question and comment. I'll try to write another part of the article with applications to these hacks! There are plenty in embedded engineering, kernel programming, cryptographic algorithms, space efficient data structures, fast image processing algorithms, and in plenty other computing areas. To answer your question, why you'd want to set/unset the right-most 1-bit, suppose you have a space efficient 8 bit data structure that represents 8 devices. Each bit represents if a device is on and off. And you want to turn off the right-most device. Then you could use that hack. Or for example, you want to linearly turn on devices from 1st to 8th, then you can just turn on the rightmost bit eight times, and turn off in the same manner. Or you could have some crazy device that puts data at some memory location and waits you to clear the rightmost bit before it puts new data at that location. Or you have a number system coded in your byte in such a way that rightmost low order bit is always the sign (or some other craziness).
- tptacek 17y agoWhen, given a bit-vector representation of 8 devices, would I want to do something with the "right-most" of those devices?
- pkrumins 17y agofor example, those 8 devices were 8 LEDs, some of them on, and you'd want to turn the rightmost led off. :) edit: i'll look into more serious applications when i write that article on bit trick applications.
- notaddicted 17y agoI was expecting to see "None of them" as kind of a joke. For a web app developer are these useful? For fun? yes. For profit? no. Title should be Low Level Bit Hacks You May Find Interesting.
- jackowayed 17y agosame here! I was hoping it would just have the title and then be a blank page.
- paulgb 17y agoI assume the title was targeted at Peteris' normal audience, not web app developers. From the about: Peteris Krumins’ blog about programming, hacking, software reuse, software ideas, computer security, google and technology.
- notaddicted 17y agoThe purpose of the Hacker News website is to serve past/present/future ycombinator candidates. I'm not even a web app developer, I wrote C code for an $8 processor today. The title (as submitted by the author of the blog) says "Absolutely Must Know," which is quite hyperbolic. I would suggest: Basic tricks of bit manipulation. Consider that this topic is covered in K. N. King's book C Programming: A Modern Approach, in Chapter 20: Low-Level Programming, on page 451
- jf 17y agoYes, even for web applications, bitwise manipulation will come in handy at some point. Personal anecdote: I recently had to combine two arbitrary unsigned 32 bit integers into one unsigned 64 bit integer to make a unique ID for an index. Not sure how I would have done that without bitwise manipulation.
- notaddicted 17y agolol. in python: (2 ^ 32)*upper + lower edit: dbl star goes blank .. so in almost python
- finger_pussy 17y agoEvery C programmer knows this stuff. (by which I mean _real_ c programmers.) This stupid article is for cock-sucking retards. (today i'm in a bad mood and really feel like flaming every nice forum there is - because it alleviates my depression. usually i'm a nice guy on hn who talks civilly but forgive me for today - sorry!)
- scott_s 17y agoIt's probably trivial for the people who run HN to figure out your real account by comparing IP addresses. If they chose to do so. You're never anonymous on the internet. Act accordingly.
- deleted 17y ago[deleted]
- moe 17y agoHow could they miss the classic. Swap two integers without a temporay var: a ^= b b ^= a a ^= b
- pkrumins 17y agooh no! totally forgot about this classic. :)
- malloc 17y agoit doesn't deserve the time... first only works if a is a different var than b second it can be much slower than typical swap... and finaly, it isn't clear what it does if your code is for others to read
- ohhellzyeah 17y agoWARNINGS: - as you excessively bit-twiddle you may end up creating nonportable code in some languages across certain platforms - surprise...you cannot manipulate a single bit of data...on most platforms the smallest bit of data you can manipulate is a word. so you may actually be creating SLOWER code while you are making BRITTLE code most of the time, bit twiddling is not worth it. sometimes it is, and it is fun.
- antipax 17y agoI guess I should be the one to provide the usual warning that C and C++ make no guarantees about the in-memory representation of the built-in types, and that this type of code can be very dangerous. It is, however, very cool when it works.
- jules 17y agoNo. They might not guarantee the representation, but they do guarantee that the operations (e.g. >> & |) work.
- scott_s 17y agoThere actually are guarantees, they're just a guarantee of ranges. (When bit-twiddling, you always want to use the unsigned version.) char is guaranteed to be at least 8 bits. short is guaranteed to be at least 16 bits. int is guaranteed to be at least 16 bits. long is guaranteed to be at least 32 bits. long long is guaranteed to be at least 64 bits. unsigned long is guaranteed to be the same size as a pointer.
- mahmud 17y agoyou want to use "unsigned" and "register".
- mahmud 17y agoyou want to use "unsigned" and "register".
- Locke1689 17y agoLook up C99 and stdint.h. You will be pleasantly surprised.
- antipax 17y agoConsider me educated.
- deleted 17y ago[deleted]
- pmorici 17y agoThis article is kind of lame. 1 - 6 should be basic skills from undergrad CS courses. Also the intro paragraph is a bait and switch, "Instead of performing some operation (such as counting the 1 bits in an integer) by looping over individual bits, these programming nuggets do the same with one or two carefully chosen bitwise operations." We never actually learn how to count set bits in an integer. (My initial thought was look-up table but is there a better way?)
- pkrumins 17y agoThere is a divide and conquer strategy, that will come in advanced bithacks article. I agree 1-5 are basic. That's why I say at #6 "Now it finally gets more interesting!!! Bit hacks #1 - #5 were kind of boring to be honest." I included them for completeness. Here is method for counting one bits: int one_bits(unsigned int x) { x = x - ((x >> 1) & 0x55555555); x = (x & 0x33333333) + ((x >> 2) & 0x33333333); x = (x + (x >> 4)) & 0x0F0F0F0F; x = x + (x >> 8); x = x + (x >> 16); return x & 0x0000003F; }
- Locke1689 17y agoIndeed. I go to Northwestern University, but I know for a fact that our first lab in Intro to Computer Systems is the same as the one at Carnegie Mellon. Basically, you're given a C file and you have to implement about 20 instructions using only specific bitwise operations and only a certain number of them. The fun part is that the number of instructions you used is posted on a website, along with the "professor's" result so you can compete against other people in the class to do it in the quickest possible fashion, but also against the professor's score. Basically, if you can't figure these out for yourself, I'm not sure you're a very good programmer.
- sgk284 17y agoThe best solution I know of is: a, i = 11, 0 while a > 0: a, i = a & a-1, i + 1 If there are k bits set out of n bits, it only does k iterations.
- ralph 17y ago
- aswanson 17y agoIs that a MOS 6502 in the image of the article? I want that chip.
- spaghetti 17y agomy favorite is determine if an int is a power of 2: if(!(a & (a-1))){ // a is a power of 2 }
- swolchok 17y agoor a is negative.