HN Explorer

Poll: How many programmers don't know about bit-wise operations?

52 points by ColinWright ↗ HN
Recently this item was submitted:

https://news.ycombinator.com/item?id=5506458

It's simple, clean, clear, and explains the first steps in elementary bit-wise operations.

For me, I learned this within hours, if not minutes, of my first encounter with the concept of computing. But I'm an old fart, and definitely behind the times. Everyone below the age of 25 has had a life full of computers, and for most people, they have no concept of how these things work, even though they use computers every day.

But programmers are somewhere in between. They don't just use computers, they make computers do things.

So what's your knowledge and experience of bit-wise operations?

81 comments

[ 3.1 ms ] story [ 137 ms ] thread
ColinWright
Clickable: https://news.ycombinator.com/item?id=5506458
jcr
At the moment, the linked submission is sitting at 2 points. The default is 1 point, and I'm the +1 up-voter. People writing code should know these things, but the move away from learning real low level languages means many people never learn these things.

NOTE: The "low level" languages are assembly, microcode, and machine code, but never C. In spite of claims to the contrary, C is a high level language.

When employers have to give tests like FizzBuzz or ask candidates if they can swap two variable without a third, then the knowledge level of "most" (self proclaimed) programmers is well below understanding bit hacks.

pjmlp
Because 90% of all programmers don't do much than writing plain CRUD applications.
pepve
I see claims like this regularly, but never any data to support it. Do you have anything to back it up?
pjmlp
Just look in any Job board.

Unless you are doing games, HPC, codecs, drivers or compilers, you seldom use this type of stuff.

yareally
I agree that it does seem that less are probably learning bitwise stuff these days. Anyone that still goes the traditional route of taking Computer Science in school is still at least exposed to them though through taking an assembly/architecture course or two. I don't use them very often still despite having seen them in those courses, but every now and then I come across somewhere they might be useful.
Someone
"People writing code should know these things"

Why? I think every programmer who didn't grow up using a machine with a few kilobytes of RAM misses out on lots of fun, and it is true that some people need to know this (e.g. to write efficient hashing code, video compressors, networking code, etc), but I also think there is a place for programmers who only work at way higher levels, glueing together libraries others wrote with a decent UI.

"if they can swap two variable without a third"

I can, but I also know it may be harder to optimize for the compiler, and introduces a data dependency that many current processors have problems handling, and I know I never felt the need to remember which those processors were. More info at http://en.wikipedia.org/wiki/XOR_swap_algorithm#Reasons_for_....

jcr
When I take a step back for wider perspective, your question "Why?" is a surprisingly good, and oddly enough, and it keeps working across the various knowledge "areas". For example, should an assembly coder know HDL (verilog/vhdl) and understand the basics of chip circuits, limits, and timing well enough to leverage them in assembly code?

Whether you're looking "down" the stack to the details of saving a "file" on a piece of rotating rust, or looking "up" the stack to the details of browsers, the question of "Why?" one should know the details of the other parts/levels is still poignant.

The most fair answer is unfortunately a wishy-washy "yes and no". There are times when having both deep and wide knowledge is extremely important, potentially even a requirement, but there are other times when the task is simple enough for it to be accomplished without extensive knowledge.

Another way to look at it is through abstractions. The entire point of abstraction is to hide enough details to make things easier. The trouble is, when abstractions fail, you really do need to know those hidden details.

Though you can often accomplish your goals without knowing all the details of the other layers, you are still better prepared by knowing them, and can be more efficient by knowing them.

BTW, Excellent link on the basic issues with XOR swapping on modern systems, but it leaves out a lot of details. ;-)

DomBlack
I have found in my time, some programmers have never heard of them, nor understand why you would ever use them. That said I've also found if you sit down with them for 5-10 minutes and explain they see the light and become interested enough to go and play with them.
anigbrowl
I like the elegance of bitwise operations and use them sometimes in signal processing applications to avoid a performance hit, though I'm no expert. But I avoid them in any high level code because a) the compiler is likely going to optimize that anyway and b) to be as human-readable as possible, the code should clearly describe the objective rather than exploit the underlying mechanism. In other words if I want to multiply or divide then I prefer to write that than rely on the reader's knowledge of what bit-shifting does, and also so that the code in question would run properly on some hypothetical ternary computer or suchlike. As I'm mainly a hobby/ad-hoc programmer I can afford not to care about the probable overhead this imposes.

Great question, I hope this stimulates some discussion.

thethomaseffect
This post illustrates my sentiment too. It's great fun to try and be clever but unless they're necessary they're probably a bad idea.
justincormack
Perfomance uses are pretty pointless now, as I discovered ten years ago when I found that gcc could turn masked shifts into a native rotate. So for multiply or divide just do so. Obviously where the underlying ops are xor etc, you use them. Most of the time I find myself using the for masking flags in system calls nowdays though and similar.
saravk
This is where macros (C) come in to play. Using macros (do all the bit shifting and masking inside) you can write very human readable code that is easy to maintain and while at the same time offers all the advantages of using bit-masks.

The major advantage of bitwise operators for me is the memory savings that come with them. I used to write the route calculation algorithms for routers and every bit/byte save had an tremendous impact on the total capacity of the router. We use bitfields to set and store various things from simple flags to multi-bit values, all inside a single integer variable.

anigbrowl
Great point and excellent context.
Joeboy
I use them lots in my hobby embedded DSP C project. I use them approximately never in my web dev day job.
zurn
This poll result will have a lot of error from self-selection.
frou_dh
I imagine the most common use of bitwise operations is setting and testing bitmasks.
vasco
I use them a lot when I'm designing hardware, but I never use them when I'm doing "regular programming", there's no reason to do it if I can use more readable, higher level constructs.
buzzkills
When writing network protocols or de-marshalling binary data it's common to want to know which bits are set in a byte. You might do a & 4 == 4 to test the 3rd bit is set, how would you do this with 'regular programming'?
altcognito
I'm guessing that writing networking protocols and even de-marshaling binary data doesn't fall under "regular programming". The vast majority of programming is business programming and marshalling and de-marshalling data is relatively troublesome (Ruby anyone?). Most of these projects are better off using a library than implementing their own.
VLM
I'm sad to say I've seen code where the answer is sprintf hex output into a temp string and some string functions to see if the last single char substring eq and/or neq certain values at the string level correlating with the 3rd bit being set (so ends in hex 2, well that means bit 3 can't be set... ends in hex 4 ding ding ding we have a winner) Only a slight upgrade in readability on a chain of mystifying if/then/else is a case statement with 16 possibilities. Only a slight upgrade on that is "optimizing" for speed by squirting out octal so your lookup stable is half the size of a hex one.
dspeyer 

    struct header __atribute__((packed)) {
      unsigned int highnibble : 4;
      unsigned int flag_foo : 1;
      unsigned int flag_bar : 1;
      unsigned int flag_baz : 1;
      unsigned int flag_qux : 1;
    }
    
    if (((header)value).flag_bar) {
pjmlp
I know them since my early ZX Spectrum and Z80 days.
shdon
((width * bytes_per_pixel)+3&~3) anyone? Can't remember how many times I've done that for Windows bitmap stride. WORD/DWORD/QWORD alignment was something I had to do frequently in C or C++ code. Even fixed point math for speed in the really old days.
zerr
hehe, also sin/cos tables ;)
dspeyer
That's a code snippet where extra parenthesis might help. The first several times I read it as:

    ((width * bytes_per_pixel)+(3&~3))
and thought "what's the point?"

I don't know why bitwise ops are so low precedence. They've always felt more like multiplication to me.

myle
I think the sample of this survey is very biased. Typical visitors of hackernews do not consist of a representative sample of programmers.
rachelbythebay
Looking at my recent projects, bitwise stuff seems to crop up when I'm dealing with binary data generated by someone else. Some of that is SmartNet trunking data - lots of weird bit-mangling happens in there. Sometimes it shows up when dealing with raw Ethernet frames. I also apparently used it to mask off all but the bottom 8 bits when creating some temporary hex identifiers with data from /dev/[u]random.

Otherwise, I'm ORing some flags together for some library call: libcurl, libxml2, plus bits of the C library like fcntl and open. Oh, and I guess I frob some termios bits sometimes to enable or disable echo for reading a password.

It doesn't come up often. When it does, it gets hidden down in some low-level utility function and then I build on top of that with something which doesn't try to be clever.

philsnow
I've found that people who list any of the following on their resume are way more likely to know how to bitwise their way out of a paper bag:

  - C (not "C/C++", those people generally mean "C++")
  - video codecs
  - compression of any kind
  - encryption / cryptography of any kind
  - embedded anything
fakeer
>>those people generally mean "C++"

I've never worked on C++(as in on commercial project or in a C++ team) however I've always mentioned it on my resume as C/C++, because I've worked on C(Kernel wrt Android and a little bit more) but for C++ I've only built one academic project(very minor) during UG and also took (2nd yr) DS in C++. I just do not want to miss a good job offer which requires C++. Because in the interview all (mostly) they are concerned about are DS/Algo etc.

So, here I intend to mean "I know C" and can work with "C++" too.

PommeDeTerre
No offense is meant, but I think you're doing yourself and potential employers a disservice by listing C++ on your resume when, based on your description, you have essentially no real-world experience with it.

There is much, much more to writing solid, production-grade C++ code than could ever be learned during a minor academic project and a single undergraduate data structures course. This is especially true with the many changes brought on recent by C++11, as well as developments within the Boost camp.

It's one thing to leave C++ unlisted on your resume, and to then bring it up during an interview. But it seems, at least to me, wrong to list it without actually having the experience (be it open source projects or past commercial work) to back up the claim.

fakeer
None taken.

You are right or you maybe right. When I joined my first job and started writing code from Day3(after initial HR/management hoopla doopla) I didn't have any commercial experience at all and I was up and going within 15 days. Must say it was a good team and now as I've experience and have some(or a little more than some) idea how things work, I believe I can pull it off.

Besides in the interviews I clearly mention the fact. It's not as if I've pasted some fictitious project/work. It's just there in C/C++. Along with Java and Python. That's it. And as I've already mentioned even when I mention C++ they test me for C only a little bit Java.

Back here, other than in startups and a few companies you are just tested for DS/Algo etc and not at all especially for a platform/technology. With the belief that the candidate will pick a language putting some effort which I believe, thought it may not be very fruitful for for a critical project where immediate expertise is required. In my last switch I was interviewed in C and worked on Java after that.

>>you have essentially no real-world experience

What do you called a real world experience? something that brought in rupees? Or sth that was used my thousands of people if not millions? Well, if that's your criteria then no I do not have real wold C++ experience.

But if you meant by sth that actually existed in real world and sth that I built from scratch and sth that was used by people - even a few, then I used my C++ text editor for over 6 months and some of my friends used it too, for some time :-)

huhtenberg
> C (not "C/C++", those people generally mean "C++")

Bzzzt... that'd be the "C++/C" people. Those who word it as "C/C++" typically meant C with reluctant C++ if pressed.

puddletown
I know how to use them but have never had a real application for them.
olalonde
Are there any use cases apart from low level C/C++ where bitwise operations are really useful? I know they are available in Ruby, PHP, etc. but it seems to me that the performance/memory gain they offer is negligible compared to the loss in readability. The last time I remember using bitwise operations was when programming an ATmega16 microcontroller.
tluyben2
I come from full time 8/16 bit assembly (Z80 and later 68000) so I tend to use those naturally. Very powerful and fun; it's a shame most universities don't teach the basics; it saves a lot of CPU cycles.
qb45
The basics don't save CPU cycles, every decent C compiler knows that for unsigned x, x*4 == x << 2.
alexbowe
I use them whenever I need to. Often I don't need to, since a compiler should be able to optimise the very basic things. Optimising prematurely is a good way to stuff something up (see question 5 here: http://ridiculousfish.com/blog/posts/will-it-optimize.html) And it hurts readability.

I would expect most good programmers to know at least some basic "tricks" though (and would hope they have the sense to not over use them).

jcr
If you're into bit hacks...

Though K&R is on the shelf within reach and I knew it had a good algorithm for counting set bits (ones), I also remembered reading about a more efficient method a while back. The following page covers a number of set bit counting hacks:

http://graphics.stanford.edu/~seander/bithacks.html

jared314
I have always wondered why I was taught binary as if they were arrays, but programming languages never allowed me to use bits like arrays. It's always masking and shifting uint16_t or int32_t, instead of what I really want,

"result = bits[3] xor bits2[3]".

jcr
The answer is hardware design. Most machines are at best "Byte Addressable" which means you have an address for a specific byte. In some cases, even if the system is "Byte Addressable" it's still actually faster to use blocks of bytes (2Byte/16bt, 4Byte/32bit, 8Byte/64bit). The reason why this is true is because the hardware design was optimized to handle blocks. Though I'm sure "Bit Addressable" hardware exists, I've never actually seen a system like that.

EDIT: You're moving stuff into and out of registers (typically blocks of specific sizes), but the registers are also not bit-addressable, hence the need for bit-wise manipulation.

arianvanp
yes, but we don't care. A language is agnostic of the underlying system. Even the C standard is built on top of a machine that doesn't really exist.

Anyhow, the point is, limitations of the underlying system aren't excuses for why this syntax isn't implemented. If I can write bitmasks, then so can a compiler, right?

winter_blue
That's why C has bit fields. It effectively lets you access individual (or clumps) of bits as elements of a struct.

Now while this may not be as "convenient" as array-style indexing, it definitely is orders of magnitude better than using bit masks and what not. You could also argue forcing to name each clump of bits (as a bit field struct forces you to) is a good thing, because most of the time the use case calls for something like this, and simply numerically indexing into bits might not be the most readable approach.

sltkr
There are tons of useful features that aren't supported in C. The basic feature set of C was determined by whatever operations Dennis Ritchie could easily implement on the PDP-11 when he created the earliest C compilers. (Fun fact: the bitwise operators even preceded the Boolean operators like && and ||.)

If the question is "why isn't bit indexing supported" then "because processors didn't (and don't) support it" is the historically correct answer, whether you like it or not.

jared314
arianvanp had the point of my question correct.
arianvanp
Now to answer your question:

Yes some languages actually support this:

http://www.erlang.org/documentation/doc-5.6/doc/programming_...

http://hackage.haskell.org/packages/archive/binary-strict/0.... (I have no idea why this isn't a Functor nor an Applicative Functor, so this is a bad example. and I know 'language features' in pure functional programming is cheating, butm eh)

http://en.wikipedia.org/wiki/Bit_field -- BE WARNED. C bitfields might give you access to bits, but they're still aligned to the boundary of your system (DWORD boundary on x86 for example)

e.g.:

    struct a {
       unsigned a: 13;
       unsigned b: 12;
    };

    sizeof(struct a) => 4;
in gcc they've got a flag to force structs to their actual bit size:

   struct a {
      ...
   }__attribute__((packed));
daeken
You can do this with bit field structs in C: http://www.cs.cf.ac.uk/Dave/C/node13.html

Super handy when you're dealing with oddly packed int representations and such.

huhtenberg
You would think so, but - No, there are no bitfield arrays. You can't have -

  struct octet
  {  
    int bit:1 [8];
  };
which is what the OP is asking for.
sltkr
The syntax you use is supported in Ruby though, which allows indexing integers to access individual bits (though as far as I know you can't create numbers that way, because integers are immutable).
informatimago
That's because you're using crude programming languages. Sophisticated programming languages let you use arrays of bits, as well as manipulating bits in integers.

    (let ((a (make-array '(4 2) :element-type 'bit
                         :initial-contents '((1 1) (1 0) (0 1) (0 0))))
          (b (make-array '(4 2) :element-type 'bit
                         :initial-contents '((1 0) (1 0) (1 0) (1 0)))))
      (list (list a 'xor b '--> (bit-xor a b))
            (list (aref a 0 1) 'xor (aref b 0 1) '--> (logxor (aref a 0 1) (aref b 0 1)))
            (list #b1100 'xor #b1010 '--> (logxor #b1100 #b1010))))
    --> ((#2A(#*11 #*10 #*01 #*00) xor #2A(#*10 #*10 #*10 #*10) --> #2A(#*01 #*00 #*11 #*10))
         (1 xor 0 --> 1)
         (12 xor 10 --> 6))
binarymax
Hackers Delight! http://www.amazon.com/Hackers-Delight-Edition-Henry-Warren/d...
buzzkills
Always just too much to justify buying. Borrowed it a few times though. These kind of problems are my crossword puzzles.
octatone2
Anyone know why bitwise AND is so slow in chrome V8 ???

http://jsperf.com/even-or-odd/2

artificialidiot
In theory js doesn't have integers. In practice, it is dependent on the available optimizations in the browser. I saw no appreciable difference on firefox, for example.
tome
There is no correct option for me. My actual answer is

"I know about them and could do complex things with them when they're the right tool, but for the kind of programs I write they're never needed."

alcuadrado
Same here, I voted the first one that seems the most closest to it.
wubbfindel
Yeah I would have voted for "I know about and use them for basic things regularly, but only rarely for complex things"

Instead I voted for the first thing.

adr_
I've forgotten when I learned this stuff. Recently, I've been teaching people who have been programming for years how to reverse engineer. It's surprising how much trouble they have grasping trivial operations like "a & a" or "b ^ b", and understanding arithmetic equivalents, like using "a << 2" to multiply by four. Two's complement also seems to challenge a lot of people - I suppose an intuitive understanding comes with time, but I'd expect people to pick that up if they've been writing C for a while.

I do feel that this poll is biased, because people prefer to declare their knowledge than admit their ignorance.

GarethElms
I used them in 1995/6 writing a DOS game while learning C and once in a C++/MFC interview question in 1998.

Never once used them in actual application development or web development since 1996. For me and the stuff I work on (web dev mostly) they're unreadable by others and any performance gains wouldn't be noticed or even cared about.

pippy
If you're not working with device drivers, embedded systems, or legacy code/filetypes you probably shouldn't be using bitwise operations. It can be confusing to other programmers, make your code a mess, and you're repeating optimisations probably found in libraries.

This is just a generalisation of course, I use them on occasion. Mostly with string encoding oddities.

For me using excessive bit operations is a red flag. I wrote a messy 1000 line file format in C, I found out by chance there was a serialization function in the library. 10 lines, done. I repeated this mistake when I started learning python (pickle, you're the best).

[deleted]
(comment deleted)