5 ms·

What 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

What 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 ago
Exactly, 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 ago
  I 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 ago
    We 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 ago
    Don'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.
DoofusOfDeath 8y ago
> I know the bitwise trick Only if you make certain assumptions about how the integer is represented, I reckon.
- projektfu 8y ago
  Indeed, a ones-complement negative number would not have this bit property.
Hello71 8y ago
In fact, newer gcc versions are unable to optimize (x & 1) == 0 at level -O1, and require -O2. I assume that the code emitted at -O2 and -O3 for both constructs is the more efficient version than the literal translation, even though they are the same number of instructions.
- BearOso 8y ago
  I highly doubt it. That’s 1:1 test eax, 1 ; use result
  - Hello71 8y ago
    gcc -O2, clang, and icc all produce the sequence: is_even(int): mov eax, edi not eax and eax, 1 ret I am far from a x86 expert, but I assume this version avoids contention on the flags registers and increases pipelining. edit: my mistake, icc and clang produce the equivalent sequence "not edi; and edi, 1; mov eax, edi; ret".
- vardump 8y ago
  Apparently not true, at least in a simple function. https://godbolt.org/g/hfpHz7 https://godbolt.org/g/hfpHz7 int isEven(int number) { return number & 1; } gcc 7.3, -O1, -O2 and -O3 (identical codegen for all optimization levels): isEven(int): mov eax, edi and eax, 1 ret
  - Hello71 8y ago
    that function checks if a number is odd, not even. https://godbolt.org/g/7Khcg9 https://godbolt.org/g/7Khcg9
    - vardump 8y ago
      My bad. Didn't even check it at any point. Anyways, 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.
throwaway2016a 8y ago
This is a question I give people who were already hired out of curiosity and I explicitly say not to use modulus. I ask a similar question in interviews but don't exclude modulus and most answer using modulus.
- naasking 8y ago
  Well, you need to use modulus if you want to be 100% portable.
dmkolobov 8y ago
always been fond of `even x = x == ((x >> 1) << 1)`

What 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 ago

Exactly, 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 ago
I 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 ago
  We 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 ago
  Don'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.

DoofusOfDeath 8y ago

> I know the bitwise trick Only if you make certain assumptions about how the integer is represented, I reckon.

projektfu 8y ago
Indeed, a ones-complement negative number would not have this bit property.

Hello71 8y ago

In fact, newer gcc versions are unable to optimize (x & 1) == 0 at level -O1, and require -O2. I assume that the code emitted at -O2 and -O3 for both constructs is the more efficient version than the literal translation, even though they are the same number of instructions.

BearOso 8y ago
I highly doubt it. That’s 1:1 test eax, 1 ; use result
- Hello71 8y ago
  gcc -O2, clang, and icc all produce the sequence: is_even(int): mov eax, edi not eax and eax, 1 ret I am far from a x86 expert, but I assume this version avoids contention on the flags registers and increases pipelining. edit: my mistake, icc and clang produce the equivalent sequence "not edi; and edi, 1; mov eax, edi; ret".
vardump 8y ago
Apparently not true, at least in a simple function. https://godbolt.org/g/hfpHz7 https://godbolt.org/g/hfpHz7 int isEven(int number) { return number & 1; } gcc 7.3, -O1, -O2 and -O3 (identical codegen for all optimization levels): isEven(int): mov eax, edi and eax, 1 ret
- Hello71 8y ago
  that function checks if a number is odd, not even. https://godbolt.org/g/7Khcg9 https://godbolt.org/g/7Khcg9
  - vardump 8y ago
    My bad. Didn't even check it at any point. Anyways, 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.

throwaway2016a 8y ago

This is a question I give people who were already hired out of curiosity and I explicitly say not to use modulus. I ask a similar question in interviews but don't exclude modulus and most answer using modulus.

naasking 8y ago
Well, you need to use modulus if you want to be 100% portable.

dmkolobov 8y ago

always been fond of `even x = x == ((x >> 1) << 1)`