test-int-log2.c

// Made for https://habr.com/ru/post/522788/
#include <stdio.h>
#include <stdint.h>
#include <math.h>
#include <time.h>
#include <sys/time.h>

uint32_t getHighBit_32(uint32_t x)
{
    x |= x >> 1;
    x |= x >> 2;
    x |= x >> 4;
    x |= x >> 8;
    x |= x >> 16;
    return x - (x >> 1);
}

uint32_t getBitCount_32(uint32_t x)
{
	x = (x & 0x55555555) + ((x >> 1) & 0x55555555);
	x = (x & 0x33333333) + ((x >> 2) & 0x33333333);
	x = (x & 0x0F0F0F0F) + ((x >> 4) & 0x0F0F0F0F);
	x = (x & 0x00FF00FF) + ((x >> 8) & 0x00FF00FF);
	return (x & 0x0000FFFF) + (x >> 16);
}

uint32_t getLog2_32(uint32_t x)
{
    return getBitCount_32(getHighBit_32(x) - 1);
}

#define N 1000000

uint32_t inputs[N];
int out1[N];
int out2[N];
int out3[N];

int64_t etime() {
  struct timeval tv;
  gettimeofday(&tv, NULL);
  return tv.tv_sec * 1000000ll + tv.tv_usec;
}

int main()
{
  int64_t t0, t1;
  for (unsigned i = 1; i < N; ++i) {
    inputs[i] = i;
  }
  t0 = etime();
  for (unsigned i = 1; i < N; ++i) {
    float r;
    long double xr;
    asm volatile(
      "fld1\r\n"
      "fildl %[ir]\r\n"
      //-"fld %%st(1)\r\n"
      //-"fstpt %[ti]\r\n"
      "fyl2x\r\n"
      "fstps %[dst]"
      : [dst] "=m" (r) //-, [ti] "=m" (xr)
      : [ir] "m" (inputs[i])
      );
    out1[i] = floor(r);
    //- if (out1[i] >= 2147483648u) {
    //-   printf("i=%u r=%.20g xr=%.30llg\n", i, r, xr);
    //-   return 1;
    //- }
  }
  t1 = etime();
  printf("With FYL2X: %lld\n", t1 - t0);
  t0 = etime();
  for (unsigned i = 1; i < N; ++i) {
    out2[i] = 31 - __builtin_clz(inputs[i]);
  }
  t1 = etime();
  printf("With builtin CLZ: %lld\n", t1 - t0);
  t0 = etime();
  for (unsigned i = 1; i < N; ++i) {
    out3[i] = getLog2_32(inputs[i]);
  }
  t1 = etime();
  printf("With habr-522788: %lld\n", t1 - t0);
  unsigned ndiff = 0;
  for (unsigned i = 1; i < N; ++i) {
    if (out1[i] != out2[i]) {
      printf("Difference: i=%u out1=%u out2=%u\n", i, out1[i], out2[i]);
      if (++ndiff >= 10) {
        return 1;
      }
    }
    if (out1[i] != out3[i]) {
      printf("Difference: i=%u out1=%u out3=%u\n", i, out1[i], out2[i]);
      if (++ndiff >= 10) {
        return 1;
      }
    }
  }
}