Check if a number is non zero using bitwise operators in C

by

The logarithmic version of the adamk function:

int isNotZero(unsigned int n){
  n |= n >> 16;
  n |= n >> 8;
  n |= n >> 4;
  n |= n >> 2;
  n |= n >> 1;
  return n & 1;
};

And the fastest one, but in assembly:

xor eax, eax
sub eax, n  // carry would be set if the number was not 0
xor eax, eax
adc eax, 0  // eax was 0, and if we had carry, it will became 1

Something similar to assembly version can be written in C, you just have to play with the sign bit and with some differences.

EDIT: here is the fastest version I can think of in C:

1) for negative numbers: if the sign bit is set, the number is not 0.

2) for positive: 0 - n will be negaive, and can be checked as in case 1. I don’t see the - in the list of the legal operations, so we’ll use ~n + 1 instead.

What we get:

int isNotZero(unsigned int n){ // unsigned is safer for bit operations
   return ((n | (~n + 1)) >> 31) & 1;
}

More Related Contents:

  1. Efficient Algorithm for Bit Reversal (from MSB->LSB to LSB->MSB) in C
  2. Arithmetic bit-shift on a signed integer
  3. Are the shift operators () arithmetic or logical in C?
  4. What is Bit Masking?
  5. Rounding up to next power of 2
  6. Catch and compute overflow during multiplication of two large integers
  7. Find most significant bit (left-most) that is set in a bit array
  8. Fast computing of log2 for 64-bit integers
  9. Extracting bits with a single multiplication
  10. SIMD signed with unsigned multiplication for 64-bit * 64-bit to 128-bit
  11. Bitwise operators and “endianness”
  12. Explain this snippet which finds the maximum of two integers without using if-else or any other comparison operator?
  13. Bitfield manipulation in C
  14. Fastest way to clamp a real (fixed/floating point) value?
  15. What does the statement if (counter & (1
  16. Finding consecutive bit string of 1 or 0
  17. set the m-bit to n-bit [closed]
  18. Bitshift and integer promotion?
  19. Unexpected C/C++ bitwise shift operators outcome
  20. Bit twiddling: which bit is set?
  21. How to define and work with an array of bits in C?
  22. Implementing Logical Right Shift in C
  23. How do I get bit-by-bit data from an integer value in C?
  24. Algorithm to generate bit mask
  25. How does this bitwise operation check for a power of 2?
  26. Decimal to Binary
  27. C Programming – XOR Bitwise Operation
  28. Bitwise shifting array of char’s
  29. How to implement Bitcount using only Bitwise operators?
  30. Order of fields when using a bit field in C

Leave a Comment