Hacker News new | past | comments | ask | show | jobs | submit login
Poll: How many programmers don't know about bit-wise operations?
52 points by ColinWright on April 7, 2013 | hide | past | favorite | 80 comments
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?

I know about them and can do modestly complicated things, but don't;
336 points
I use them all the time, and do complex things with them when they're the right tool;
199 points
I know a bit about them, but wouldn't really know how to use them "in anger";
176 points
I know of them, but can't use them;
73 points
I found that submitted item really interesting, and want to learn more;
28 points
I found that submitted item to be entirely new to me, but don't really want to know more.
13 points



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."


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.


Same here, I voted the first one that seems the most closest to it.


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


> 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.


>>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.


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.


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 :-)


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.


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.


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.


Great point and excellent context.


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.


Hackers Delight! http://www.amazon.com/Hackers-Delight-Edition-Henry-Warren/d...


Interesting book but wow $50, never seen anything so expensive, even used copies are over $25 ?

Discovered my library allows me read it for free online:

http://proquestcombo.safaribooksonline.com/9780133084993

Others can at least see the table of contents.


Always just too much to justify buying. Borrowed it a few times though. These kind of problems are my crossword puzzles.


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.


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'?


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.


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.


    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) {


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]".


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.


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?


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.


arianvanp had the point of my question correct.


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));


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.


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))


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).


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.


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.


This question isn't exactly clear either. What constitutes "knowing" bit-wise operations? Can I do bit-wise math? Test if a bit is set? Use shift operators for some arcane purpose?

As I get older (lets just say I'm over 35), I'm baffled by older programmers who worry about this stuff. When you were a young programmer, there were likely problems that were solved that you never had to deal with that older programmers feel were super important. Bitwise operations likely stick around for the duration of digital computing, but I think it's foolhardy to think that the vast majority of developers will need to know about them in all their gory detail.

New developers will stand on the shoulders of giants so to speak, and solve the problems that are pertinent to their domain. It may or may not include bit-wise operations.


I think the sample of this survey is very biased. Typical visitors of hackernews do not consist of a representative sample of programmers.


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


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.


"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_....


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. ;-)


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.


Because 90% of all programmers don't do much than writing plain CRUD applications.


I see claims like this regularly, but never any data to support it. Do you have anything to back it up?


Just look in any Job board.

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


I use bitwise operations whenever they make sense. Usually, this is abstracted behind the scenes, since most people aren't going to care about messing with bits.

For example, the WordPress JSON API I've been working on [0] uses them for HTTP methods. This lets me have an EDITABLE, which is actually just POST | PUT | PATCH. With the bit fields, a user can also indicate whether an endpoint expects JSON data and whether it should be hidden from indexes.

It's certainly possible to do all of this without bitmasks, but I personally think `EDITABLE | ACCEPT_JSON | HIDDEN_ENDPOINT` looks nicer than `array('methods' => array('POST', 'PUT', 'PATCH'), 'accept_json' => true, 'hidden' => true)`

[0]: https://gist.github.com/rmccue/5022591d312952d1245a#file-wp-...


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.


I know them especially since I took digital electronics in university. However, I've never had to use them so far in anything I've built. I could use them if required but unless I get into some kind of video processing or high end optimization, I don't think it'll be required.


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.


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).


I believe my introduction to bit shifting is wrapped up somewhere in the quagmire of my first few months of computer science in college. But I actually became pretty comfortable with their usage since the first major piece of software I worked with, vBulletin, made extensive use of bitwise operations in the ACL and options matrices.

It was a super fast, if visually opaque, way of doing the calculations required to facilitate a very complex permission system. I imagine Facebook works in a similar way, if on a somewhat grander scale.


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).


This poll result will have a lot of error from self-selection.


Having done a significant amount of assembly language programming in the past, understanding bit-wise operations is required. In my first job out of college, I was parsing bytes of data where each bit represented a multiple choice answer to a question. So, yea I'm tight with bit-wise operations. And, I'm glad that I have this knowledge, because a good deal of Raspberry Pi projects, where I'm parsing data from a chip on the i2c bus, require it.


The original article by was on how compilers did optimizations using bitwise operations, which makes perfect sense. In day to day programming they can be useful, but all too often I run into code where they've obfuscated what's going on being clever with their operators, bitwise included. If the compiler can optimize it for us, write something clear and and obvious but not necessarily optimal. Code is for people.


I guess programming languages don't really encourage using bit wise operations.

On top of it, it doesn't have many advantages. It takes much less memory, but takes more lines to write, while on the hardware, it's the opposite: more memory, not so fast processors.

What always bugged me, is that there are no real programming facilities to take advantages of bits, like encoding many variable in on 32 bit integer variable.

I guess


Although not part of the language proper, C++'s STL has vector<bool> that packs boolean flags into a bitvector (a now regrettable optimisation, since it doesn't function the way a container should - a story for another time). There is also bitset, which is similar but static.

Erlang has a beautiful language feature for this: http://www.erlang.org/doc/programming_examples/bit_syntax.ht... It uses pattern matching to unpack variable length fields in a bitvector. So beautiful.

Edit: Check arianvanp's post above https://news.ycombinator.com/item?id=5506902


IMO, bitmasks are a more interesting and useful example of "bit level" programming. This is all because of this statement:

"Most compilers realize this and change our code to something like:"

I agree that it's important that we know, and keep in mind, what is going on behind the curtain, but using bitwise operations that would otherwise be performed by the compiler introduces uneccessary complexity.


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


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.


Bitwise operations are still common and necessary in dealing with matrices and arrays in Matlab/numpy etc.For ordinary code they would be an unnecessary layer of complexity and perhaps even a false source of optimisation.I tend to trust that the language designers know what they are doing more than I do by default at that level of abstraction.


In the videogame industry the standard question on the phone screen interviews is what is the two power 8. It's eerie how many people cannot answer this at all or answer incorrectly.

So, if even the people who are aspiring to write "code to the metal" console games don't know binary then, I imagine, a generic programmer knows it even less.


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.


I use them lots in my hobby embedded DSP C project. I use them approximately never in my web dev day job.


I use them all the time but I do so in embedded environments where memory (and efficiency) is tight, and bitwise operations are always needed to access the hardware registers.

I see little use for it in other applications, unless these are extremely demanding (such as graphics engines).


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.


((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.


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.


hehe, also sin/cos tables ;)


If you are interested in learning additional bit-wise operations, this is a very-well curated collection of such tricks http://graphics.stanford.edu/~seander/bithacks.html


I use "&" and "|" when i use enums, that act as options. I.e. var myCarExtras = Extra.Radio | Extra.PowerWindows;

Where Extra = { Radio = 1, PowerWindows = 2, Tint = 4, Rims = 8 };

Then I can do: if (Tint | powerWindows) { return totalPrice + 1000; }


C# programmer? I think this is one of the nicer little features in that language.


I imagine the most common use of bitwise operations is setting and testing bitmasks.


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.


The basics don't save CPU cycles, every decent C compiler knows that for unsigned x, x*4 == x << 2.


For better or worse, where I work all developer candidates are asked for a program to count the number of 1 bits in a 32 bit unsigned integer. Only about 1 in 5 can provide one.


For me they are like regular expressions. It takes quite some time to process and understand their function in programs. So I rather avoid them.


Anyone know why bitwise AND is so slow in chrome V8 ???

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


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.


I can use them to do math

Mostly just multiplication and division by 2,4,8,16,32....


I know how to use them but have never had a real application for them.


I find them useful in my job. I work in parimutuel betting.


I know them since my early ZX Spectrum and Z80 days.




Consider applying for YC's Spring batch! Applications are open till Feb 11.

Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: