1

Is there a fast way to find if a 32-bit integer is a multiple of 4 without using the % operator (In C++)?

4
  • 4
    If you want to C++ solution, why do you has tagged C?
    – Jack
    Commented Jul 11, 2012 at 15:48
  • 1
    Why not use the % operator? When you have a tool that's specifically designed for precisely the task at hand, you have to wonder when someone specifically insists you not use it. Commented Jul 11, 2012 at 15:59
  • I thought that the % operator would be slow because it uses divide (I think?)
    – Tom Tetlaw
    Commented Jul 11, 2012 at 16:18
  • 1
    @TomTetlaw: Compilers are written by smart people. If the language presents a clean, simple, direct, obvious way to do something, why would you assume it would be badly implemented? On a version of GCC I just tested on, return (c%4) == 0; and return (c & 3) ==0; produce identical code. The compiler knows they're equivalent. Both became two assembly instructions, andl then sete. Commented Jul 11, 2012 at 20:37

1 Answer 1

22

yes, there is.

((i & 3) == 0)

Note that this may not be any faster. Also a good optimizing compiler will convert your modulus against constant 4 to the fastest operation anyway, so it may well generate this automatically.

Check the generated code if you are interested.

2
  • And it's not actually guaranteed to work by the C++ standard, although only for the rather unlikely reason that C++ implementations are permitted to use 1s' complement representation of negative integers. Commented Jul 11, 2012 at 16:14
  • I tested on GCC 4.6.3 and identical code was produced. The compiler is smart enough to know that a constant modulus that's a power of two is identical to a bitwise AND with a number one less than the modulus on that platform. (Interestingly, andl on x86_64 and testb on x86_32. Go figure.) Commented Jul 11, 2012 at 20:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.