Four methods to test if an integer is a power of two.

is_pow_of_2.c

/**
 * Four methods to test if an integer is a power of two.
 * Compile with `-march=haswell`.
 */

#include <stdlib.h>
#include <stdio.h>
#include <immintrin.h>
#include <time.h>

/* All functions need to check for non-zero first, otherwise those bit
   tricks would consider 0 a power of two otherwise. */

_Bool test_1(int x) {
  return x && !(x & (x-1));
}

_Bool test_2(int x) {
  return x && (x & -x) == x;
}

_Bool test_3(int x) {
  /* BSR returns the bit index of the most significant bit, BSF of the least
     significant bit. */
  return x && _bit_scan_reverse(x) == _bit_scan_forward(x);
}

_Bool test_4(int x) {
  /* BLSR is a Haswell instruction, equiv to x & (x-1) */
  return x && !_blsr_u32(x);
}

_Bool test_naive(int x) {
  int a = 1;
  for (int i = 0; i < 32; ++i) {
    if (x == (1 << i))
      return 1;
  }
  return 0;
}

_Bool run_tests(_Bool (*test_f)(int)) {
  for (int i = 0; i < (1 << 31); ++i) {
    if (test_naive(i) != test_f(i))
        return 0;
  }
  return 1;
}

clock_t time_test(_Bool (*test_f)(int), int count, unsigned seed) {
  _Bool volatile r; /* I think that should make the func call actually happen */
  clock_t start;
  srand(seed);

  start = clock();
  while (count-- > 0) {
    r = test_f(rand());
  }

  return clock() - start;
}

int main() {
  const unsigned times = 10000000;
  int x;

  printf("correctness: %d %d %d %d\n",
         run_tests(test_1),
         run_tests(test_2),
         run_tests(test_3),
         run_tests(test_4));


  printf("speed (%9u iterations): %d %d %d %d\n",
         times,
         time_test(test_1, times, 1),
         time_test(test_2, times, 1),
         time_test(test_3, times, 1),
         time_test(test_4, times, 1));

  return 0;
}