Some would call it math.
But I guess that shows you the state of our art.
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.
Only if you make certain assumptions about how the integer is represented, I reckon.
int isEven(int number)
{
return number & 1;
}
isEven(int):
mov eax, edi
and eax, 1
retAnyways, you still prove my point. All those three are pretty close.
-O1 sete instruction is very slightly unoptimal, but even it is just a fractional clock cycle.
test eax, 1
; use result is_even(int):
mov eax, edi
not eax
and eax, 1
ret
edit: my mistake, icc and clang produce the equivalent sequence "not edi; and edi, 1; mov eax, edi; ret".
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.
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?
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?!)
For the machine learning and infrastructure work I've done the last 5 years or so I haven't had to do even a single bitmask, shift, etc. directly. Of course we use these things liberally (e.g. hash functions) but it's hardly necessary to write the code itself very often, even in very sophisticated applications.
Javascript only has doubles so you can't even bit twiddle if you wanted - C programmers can't even imagine.
It doesn't have integers to store.
JavaScript's numbers can do everything doubles can; but if the compiler can prove that all values that a particular variable could possibly take on will fit in a smaller type, then it can use that. So a variable really can end up stored as an integer--or never stored anywhere for that matter, like if a loop gets unrolled and the counter is optimized out.
The bitwise operators behave as if integers are 32-bit two's complement. The typed arrays are also two's complement. A smart developer can write code that a smart compiler will compile to bitwise operations on actual physical 32-bit integers.
https://developer.mozilla.org/en-US/docs/Web/JavaScript/Refe...
https://v8project.blogspot.com/2017/09/elements-kinds-in-v8....
Most C programmers would be too scared to perform bitwise operations on doubles and JS doesn't add anything that makes it safer.
The problem happens when you treat numbers one way and they are treated differently elsewhere. For example -0 when undergoing a bitwise +/- check (val & (1U<<31)) will appear positive when its negative by definition.
The cast to an integer prior to the bitwise operator looses information. You can use the operators safely if you know there is no information to be lost, but it is not type checked like with C. I will say at least JavaScript guarantees twos compliment. You never know when your favourite compiler will decide to break your code in the name of a faster benchmark - correctness of existing programs be damned. Implementation defined used to mean do something sane, but I digress.
((int)dblval) & flag
would require serious justification in a C code review. In JS its all you have. Under those restrictions I'd use it as rarely as possible. But yes you can use it correctly if you try.
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.
state = state & ~BIT7;
state = state.without(BIT7);Plus there are performance concerns. I remember one graduate introducing a c++ bit field class and tried to replace some core functionality with it and killed performance. Developers prefer to debug non optimized builds, and non optimized builds can end up running slow when you replace simple one liners with classes and inline methods that don't get optimized in debug builds.
[1]I hope this doesn't sound aggressive as it really isn't intended to. It is just everyone is so used to seeing bitwise operations it is as straight forwards as reading "set the third bit" or "toggle the last bit" when we see the C code.
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.
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.
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.
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.
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.
>>> -4%2
0
>>> -8%2
0
>>> -9%2
1 ?- x is -4 mod 2.
X = 0.
?- X is -8 mod 2.
X = 0.
?- X is -9 mod 2.
X = 1.
?- X #= 2*_.
For example:
?- -4 #= 2*_.
true.
?- -9 #= 2*_.
false.
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.
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-in...
(-123 % 2 == 1).Dump();
% in C# is the remainder operator, not canonical modulus.
>> -2 % 2
-0
>> -3 % 2
-1
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...
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.
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.