5 ms·

Here's a much more comprehensive collection of bit hacks: http://graphics.stanford.edu/~seander/bithacks.html http://graphics.stanford.edu/~seander/bithacks.ht

Here's a much more comprehensive collection of bit hacks: http://graphics.stanford.edu/~seander/bithacks.html http://graphics.stanford.edu/~seander/bithacks.html

benhoyt 16y ago
Yeah, that's a better one, with more actual hacks. Most of the "hacks" in the original post weren't really hacks, but the way embedded programmers set and toggle bits every day.
alextgordon 16y ago
It depresses me that something as simple as int mask = v >> sizeof(int) * CHAR_BIT - 1; unsigned int r = (v ^ mask) - mask; can be granted a patent (http://graphics.stanford.edu/~seander/bithacks.html#IntegerAbs http://graphics.stanford.edu/~seander/bithacks.html#IntegerA...).
- yason 16y ago
  Granted, yes. There was discussion about whether the patent is at all valid, given abundant prior art. However, it depresses me too because you probably need lots of money and possibly a lawsuit to settle out the validity issue.
IgorPartola 16y ago
Ha. Next time someone asks how to swap two values at an interview question (I think this is pretty common): #define SWAP(a, b) (((a) ^= (b)), ((b) ^= (a)), ((a) ^= (b)))
- cs_loser 16y ago
  Is it pretty common? As someone who does a fair number of software engineer interviews, that's a trick question. The real answer to "swap two vars with no temps" is: 1. Don't be clever in our code base. Use a temp variable. 2. There's various dumb tricks with XOR, and possibly add/subtract if overflows don't break. 3. A sequence of several instructions where each of them requires the result of the previous one may not execute particularly fast on modern processors. Instruction/cycle counts -- like 3 -- are great when there's no pipeline and no cache, but otherwise pretty much useless. 4. The things you're swapping might be local variables, and when the compiler has -O <anything> specified, local variables start getting weird, and "swap" can sometimes be done in zero instructions, namely by the compiler noting that they have now been swapped and using the other one for the rest of the basic block. (or further dominated basic blocks for that matter) 5. If the things you're swapping are in main memory, or even if it's not in L1, you're going to be incurring a cost much greater than the temporary use of a register. (and, if you don't know where they are and it might be main memory, this might dominate the average runtime) The answer is definitely not "three xors".
  - TimMontague 16y ago
    Most of the hacks in that guide assume that you don't care about readability or even portability to a certain extent. It certainly isn't everyday that you need to optimize your code at that level, but in some instances it could be useful (for example trying to reduce delay in a real-time program.)
  - mentat 16y ago
    Embedded and firmware engineering questions expect this as an answer. Anyone following your advice will not be taken seriously. This is true regardless of whether you're correct factually. Readers of this thread deserve to know that.
    - leif 16y ago
      3 is actually a quite valid point for embedded. Any swap actually will be expensive when it comes to keeping cache lines clean. The correct answer in that case is just to not swap the variables, and instead swap their uses later on: int x, y; ... SWAP(x, y); foo(x, y); becomes int x, y; ... foo(y, x); (naturally, this is why I still eagerly await the arrival of a C compiler that has macros with LISP power)
      - pjscott 16y ago
        In that case, you can get the right behavior by just swapping the variables using a temporary variable. If the compiler is decent, it'll automatically swap their uses later on. I don't know how every compiler works, but if you use Clang (or anything LLVM-based), it converts everything to Single Static Assignment (SSA) form: int x1 = 42, y1 = 666; ... int tmp = x1; x2 = y1; y2 = tmp; // SWAP(x, y) foo(x2, y2); In SSA form, the value of a variable does not change, so it ends up creating a bunch of "imaginary" variables to hold intermediate values. From there, it does optimizations, then figures out how best to allocate registers, and what needs to be stack-allocated.
        leif 16y ago
- RiderOfGiraffes 16y ago
  As an interviewer, the real value in this question is to get the attitude of the person behind it. The best candidates know it because they've read widely and know the tricks. They also then add "But I wouldn't use it." The very best candidates add: Because it's tricky, hard to read, limited in scope, and usually you can avoid swapping variables by changing their usage downstream. Besides, the best compilers will sort it out for you if you write it clearly and cleanly. When I interview it's not the answers I listen to, it's the knowledge they expose, not of programming per se, but of good practices in programming.

Here's a much more comprehensive collection of bit hacks: http://graphics.stanford.edu/~seander/bithacks.html http://graphics.stanford.edu/~seander/bithacks.html

benhoyt 16y ago

Yeah, that's a better one, with more actual hacks. Most of the "hacks" in the original post weren't really hacks, but the way embedded programmers set and toggle bits every day.

alextgordon 16y ago

It depresses me that something as simple as int mask = v >> sizeof(int) * CHAR_BIT - 1; unsigned int r = (v ^ mask) - mask; can be granted a patent (http://graphics.stanford.edu/~seander/bithacks.html#IntegerAbs http://graphics.stanford.edu/~seander/bithacks.html#IntegerA...).

yason 16y ago
Granted, yes. There was discussion about whether the patent is at all valid, given abundant prior art. However, it depresses me too because you probably need lots of money and possibly a lawsuit to settle out the validity issue.

IgorPartola 16y ago

Ha. Next time someone asks how to swap two values at an interview question (I think this is pretty common): #define SWAP(a, b) (((a) ^= (b)), ((b) ^= (a)), ((a) ^= (b)))

cs_loser 16y ago
Is it pretty common? As someone who does a fair number of software engineer interviews, that's a trick question. The real answer to "swap two vars with no temps" is: 1. Don't be clever in our code base. Use a temp variable. 2. There's various dumb tricks with XOR, and possibly add/subtract if overflows don't break. 3. A sequence of several instructions where each of them requires the result of the previous one may not execute particularly fast on modern processors. Instruction/cycle counts -- like 3 -- are great when there's no pipeline and no cache, but otherwise pretty much useless. 4. The things you're swapping might be local variables, and when the compiler has -O <anything> specified, local variables start getting weird, and "swap" can sometimes be done in zero instructions, namely by the compiler noting that they have now been swapped and using the other one for the rest of the basic block. (or further dominated basic blocks for that matter) 5. If the things you're swapping are in main memory, or even if it's not in L1, you're going to be incurring a cost much greater than the temporary use of a register. (and, if you don't know where they are and it might be main memory, this might dominate the average runtime) The answer is definitely not "three xors".
- TimMontague 16y ago
  Most of the hacks in that guide assume that you don't care about readability or even portability to a certain extent. It certainly isn't everyday that you need to optimize your code at that level, but in some instances it could be useful (for example trying to reduce delay in a real-time program.)
- mentat 16y ago
  Embedded and firmware engineering questions expect this as an answer. Anyone following your advice will not be taken seriously. This is true regardless of whether you're correct factually. Readers of this thread deserve to know that.
  - leif 16y ago
    3 is actually a quite valid point for embedded. Any swap actually will be expensive when it comes to keeping cache lines clean. The correct answer in that case is just to not swap the variables, and instead swap their uses later on: int x, y; ... SWAP(x, y); foo(x, y); becomes int x, y; ... foo(y, x); (naturally, this is why I still eagerly await the arrival of a C compiler that has macros with LISP power)
    - pjscott 16y ago
      In that case, you can get the right behavior by just swapping the variables using a temporary variable. If the compiler is decent, it'll automatically swap their uses later on. I don't know how every compiler works, but if you use Clang (or anything LLVM-based), it converts everything to Single Static Assignment (SSA) form: int x1 = 42, y1 = 666; ... int tmp = x1; x2 = y1; y2 = tmp; // SWAP(x, y) foo(x2, y2); In SSA form, the value of a variable does not change, so it ends up creating a bunch of "imaginary" variables to hold intermediate values. From there, it does optimizations, then figures out how best to allocate registers, and what needs to be stack-allocated.
      - leif 16y ago
RiderOfGiraffes 16y ago
As an interviewer, the real value in this question is to get the attitude of the person behind it. The best candidates know it because they've read widely and know the tricks. They also then add "But I wouldn't use it." The very best candidates add: Because it's tricky, hard to read, limited in scope, and usually you can avoid swapping variables by changing their usage downstream. Besides, the best compilers will sort it out for you if you write it clearly and cleanly. When I interview it's not the answers I listen to, it's the knowledge they expose, not of programming per se, but of good practices in programming.