20 ms·
I 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 la
by throwaway2016a 8y ago
I 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.
- bakery2k 8y agoGuido has written a blog post explaining "Why Python's Integer Division Floors" [1]. Python also uses floor division, and the corresponding "sign-of-modulo matches sign-of-divisor", for floating-point numbers. The blog post claims that this can be problematic in certain cases (compared to C's "sign-of-modulo matches sign-of-dividend"), but does not give any concrete examples. [1] http://python-history.blogspot.com.au/2010/08/why-pythons-integer-division-floors.html http://python-history.blogspot.com.au/2010/08/why-pythons-in...
- kazinator 8y agoISO C doesn't leave it up to the hardware. Integer division is required to truncate toward zero; the remainder harmonizes with that. (If someone designs a new HLL which leaves some arithmetic to the hardware that C doesn't, that is indeed silly.) The sane language here Common Lisp: it does it in all the ways rather than picking one approach with some hand-waving justification about why it's the good choice. It has truncate, round, ceiling and floor functions that all return a quotient and remainder. There are also mod and rem functions that calculate just the remainder from a floor and truncate, respectively.
- LandR 8y agoIn C# this would be wrong (-123 % 2 == 1).Dump(); Prints False. % in C# is the remainder operator, not canonical modulus.
- deleted 8y ago[deleted]
- craftyguy 8y agoWell that's not confusing at all. Why would C# change the definition of a common operator character?
- bjoli 8y agoI think you would be surprised if you started looking around to see how how % is handled.
- tonyarkles 8y agoJavascript as well: >> -2 % 2 -0 >> -3 % 2 -1 Edit: well, at least in Firefox JS. I have no idea if that's actually standard-mandated behaviour or if it's an implementation quirk. The -0 is especially weird (I had written odd but...)
- justin66 8y agoThis is pretty interesting. I don't use js but I took a quick look and apparently (x % 2) == 0 as a test for even integers should still work properly there, since a comparison of -0 and 0 will consider them equivalent.
- justin66 8y ago> I would think a "if (x % 2 == 1) //odd" would be within the realm of most CS applicants. Yeah, if they can pass a fizzbuzz question they can probably get that. At which point it behooves the interviewer to explain why (x % 2) == 0 to find an even number is a better test...
- throwaway2016a 8y agoThey couldn't offer an answer using bitwise operators. They knew mod 2. Most web developers (front and backend) will never use bitwise and many don't have college degrees so they didn't use it in college. It is actually quite understandable that they won't. I've used bitwise here and there in backend code in my 20+ years of web dev but never in a case where it couldn't be rewritten as slightly less efficient but more readable code.
- ladberg 8y agoWhat did they usually say? I know the bitwise trick, but I would say "x % 2 == 0" if asked because it makes a lot more sense and will (almost) always compile to the exact same code.
- carlmr 8y agoExactly, readability by other engineers + compiler optimizations is usually better than some bithacking that may or may not help in terms of speed and definitely doesn't help with understanding. (In this case maybe simple enough, but still).
- mbrumlow 8y agoI am not trying to start a argument but it is a bit sad that these things are called "hacks", in the article, and by others. Some would call it math. But I guess that shows you the state of our art.
- blackflame7000 8y agoWe live in the era were you can get a Billion Bytes for a dollar. We also live in an era where finding someone who can manipulate bits to improve performance is either 1)A Micro-Op 2) Extremely fringe work, or 3) prohibitively expensive to be worth it.
- carlmr 8y agoDon't get me wrong. I find most of these "bit hacks" to be quite simple individually. But they add a layer of necessary comprehension. In most cases you won't see these alone. They will be surrounded by tens of thousands of other lines of code. And where there is one "hack" there are usually others. And at some point you end up with a bug somewhere because one of these smart little hacks is failing. You don't know which one. This does create unnecessary problems for maintenance in the future. So use it, but use it only when absolutely necessary. Not because you think the code will run faster. It's also important to note that many things people think make the code faster, don't. Like vector vs. linked list access. Intuitively the linked list seems much simpler for inserting an element. But in almost all cases the vector is faster, because of cache locality. So what I'm saying is. Do things that make the code probably faster like using a vector, if they don't cloud understanding. If they do, leave them out until you have a reason to use them. The only reason to use micro-optimizations like these is if you measured execution time and know there is a performance bug in this place in the code which your "hack" could resolve. No measurement -> no optimization. Because the performance problems are almost always in different places than the average developer assumes. And then add a comment explaining what you did to a 5 year old.
- debatem1 8y agoThis was literally part of my first programming assignment in college. Can people really not do this? Isn't fizzbuzz considered too obvious these days? I feel like I must be misunderstanding...
- throwaway2016a 8y agoAgreed. I had to do this first semester freshman year and again in my embedded systems courses. But a very large portion of web developers never went to college or only have a 2 year degree (and, sorry, but most 2 year "Computer Science" degrees glorified really expensive bootcamps).
- muddyrivers 8y agoYou miss the point. I learned all these tricks in school as well. I loved them. I felt "smart". After working for so many years, I only remember the basic ones. If you ask me the "smart" tricks, I can't get them right out of my head. I can sit down with a piece of paper and may get them after trials and errors after a while. Guess what, the important thing is I know these "smart" tricks exist. If I need them in real work, I can google them out easily. Why need I remember them? In my real work, what I need to get right out of my mind are how our systems work, how MySQL/Postgres/Hadoop/HBase/Kafka/Spark/Linux/AWS/... work, etc.
- Silhouette 8y agoAfter working for so many years, I only remember the basic ones. Several of the examples in the article are the basic ones, though: test, set, clear or toggle a bit. You might not remember the trick for finding the least significant 1 bit, but it's not as if testing whether a number is odd or even is some sort of arcane knowledge. Anyone who has to resort to Google or Stack Overflow for something so simple is going to struggle in large parts of the programming industry.
- Insanity 8y agoHow do you phrase the question? Because surely people you hired should have been able to answer it using modulus?
- throwaway2016a 8y agoSee my note. I don't ask the question in interviews. I think it is useless, they don't need it for their job. I do ask a variant of fizz buzz that requires using modulus. They don't get hired if they can't answer that one. So this subset of people I'm talking about are ones who do know modulus.
- MarkMMullin 8y agoI ask it sometimes too - my favorite response opened with 'you want maintainability or speed' So I picked speed. They immediately set the first branch at mod 3 with the obvious justification - hired on the spot :-)
- deleted 8y ago[deleted]
- barrkel 8y agoOnly a month or two ago I had to debug a data roundtripping issue with our Hadoop cluster. Decimals being sent in came back as apparently completely random numbers. More experimentation revealed it was only negative numbers that were being messed up (the original tests passed with positive numbers). Further bitwise investigation and manual twos-complement calculation, and I discovered the problem to be a mismatch in fixed point precision, where negative numbers weren't being sign extended correctly. It's not every day you rely on your binary calculation skills, but it does come up.
- emilfihlman 8y agoIf what you say is factual I'm astonished at the level of incompetence.
- ex_amazon_sde 8y agoI interviewed many tenths of candidates at Amazon and I never met one who didn't know the very basics of binary numbering.
- throwaway2016a 8y agoUsing the word incompetence is ridiculous. An incompetent person can't do their job and I can tell you all these people were very competent at their job. They just didn't ever have the need to learn binary math. Bitwise math is not needed for a huge portion of software. That's like saying someone is incompetent because their entire career they have only spoken English and someone writes "el al." to them and they don't know what it means. Sure english is based on latin. Do most english speakers know enough latin to know what "et al." means? Probably. Does that make the person incompetent at their job where they only need to speak English? Definitely not. A large portion of web developers don't have any formal education and the bootcamps and websites don't teach this stuff. As someone who has a computer science degree it seems absurd, one might even say it sounds like incompetence, but it is actually completely understandable. Most of them can come up with the modulus solution but the bitwise operator solution is less common. To the other comment in reply to you that talks about Amazon... yeah, that is Amazon... I work for a company with 1/100,000,000 the budget of Amazon (wild probably inaccurate guess). We don't get the people Amazon attracts. We get the people who all those other companies turned down. But you know what? With extremely few exceptions all of them have been great software developers despite not knowing how to tell if a number is even or odd using bitwise.
- rahilb 8y agoThis is useful to know for counting the bits set in a word.
- CapacitorSet 8y agoWhich isn't super helpful, because there is [a GCC `__builtin_popcount`](https://gcc.gnu.org/onlinedocs/gcc/Other-Builtins.html https://gcc.gnu.org/onlinedocs/gcc/Other-Builtins.html), a POPCNT intrinsic if you're developing for SSE4, and [existing implementations](https://en.wikipedia.org/wiki/Hamming_weight#Efficient_implementation https://en.wikipedia.org/wiki/Hamming_weight#Efficient_imple...) you can look up at any time if you don't want to reinvent the wheel.
- rahilb 8y agoThat's cool. I probably shouldn't have said useful and instead said interesting. My interest in these kind of operations is to learn lower level theory, not to produce production grade bit counting/twiddling code. In that sense, the operation is interesting (to me).
- hedora 8y agoThe “clear the bottom bit” hack is pretty cool. It’s sometimes faster to roll a loop that uses that than to invoke the GCC popcnt intrinsic. If you pass an -march parameter that lets GCC emit the intended intel assembly instruction, then the intrinsic seems to always win (as expected!)
- scraft 8y agoIn the computer games industry, or at least at the companies I have worked in based in the UK, these would be part of a test given either remotely or immediately on arrival and failing to answer correctly would make it unlikely to proceed any further. In the c/c++ game code bases I have worked on, it is very common to have statuses stored as a uint with each bit representing something and very common to set, unset, toggle, reverse bits etc. I actually read the first part of the article thinking these aren't hacks these are just things people use day in day out. But the later section about setting last 0 or 1 bit etc suddenly because things I wouldn't typically see in the wild.
- majewsky 8y agoAt least in C++, wouldn't you just write these "hacks" only once, in inline methods of a BitField class? It's much more likely to mistype state = state & ~BIT7; than to mistype state = state.without(BIT7);
- dahfizz 8y agoWould you create a wrapper class and member function to make addition less likely to mistype? num = num.plus(x); might be less likely to mistype than num = num + x; but nobody would ever do that. Once you've done bitwise operators a few times they become just as comfortable and natural as addition or subtraction.
- daemin 8y agoNope, people actually just write the bit setting code. It's simpler and also I haven't found a good generic bit flags class that works as you intend.
- slededit 8y agoWhat about C++ bitfields? Not a library but a language extension. A lot of code I used has migrated to that.
- 8y ago
- mathattack 8y agoHow often are bloggers really aware of what we MUST know or do?
- OskarS 8y agoCome on, really? "Knowing the very basics of binary numbers" isn't some obscure super-technical skill when it comes to programming, it's fairly fundamental. If they don't know that, then how can they possibly know how to use bit-masks, for instance? Like, I get it when people say "most of the stuff you learn getting a CS degree has very limited usefulness day to day". Sure, you're not going to be implementing red-black trees or skip lists in your day-to-day, but you can't possibly claim that having a basic idea of how the bitwise operators work (or the details on how numbers are represented in binary) is in the same category.
- juliangoldsmith 8y ago>how can they possibly know how to use bit-masks, for instance? Given that most programming jobs are web development jobs (I think, I don't have numbers to back that up), what makes using bit-masks important? That is, why would someone working on a web application need to know how to use them?
- phaemon 8y agoSo that they understand how a network mask works? I'm assuming if you're working on the web you ought to know something about networks, right?
- juliangoldsmith 8y agoWhy would a regular web developer need to know anything about network masks? Those come up in administration, but generally not in development.
- tonyarkles 8y agoI might be asking a bit much here, but I generally expect someone who's developing something that's going to run on the Internet to have some understanding of how the Internet works. Like... you don't need to understand the intricacies of BGP, but some idea of how a request from your web browser leaves your home network and comes back is strongly appreciated. My biggest reasoning for desiring that skill is debugging. If you build a system and it doesn't work right for whatever reason, it's good to understand why that might be. Also, having some appreciation for that stuff really helps you make good decisions (but why can't I make 200 HTTP requests while loading my page?!)
- paddyredbeard 8y agoI've been finding more & more in new hires that what they know coming in sometimes isn't as important as their willingness to continue learning. If they admit they don't know how to answer a question but are willing to give it a try, that's usually a good sign.