Fast integer log10 in C

log10.c

#include <stdint.h>

/*
 
  Fast 64bit integer log10
  WARNING: calling ilog10c(0) yields undefined behaviour!

  On x64 this compiles down to:

  pushq	%rbp
  movq	%rsp, %rbp
  bsrq	%rdi, %rax
  xorq	$63, %rax
  movl	%eax, %ecx
  xorl	$63, %ecx
  leal	(%rcx,%rcx,2), %ecx
  movl	$3435973837, %edx
  imulq	%rcx, %rdx
  shrq	$35, %rdx
  leaq	_ilog10c.thr(%rip), %rcx
  cmpq	%rdi, (%rcx,%rax,8)
  setbe	%al
  movzbl	%al, %eax
  addl	%edx, %eax
  popq	%rbp
  ret
	
*/

uint32_t ilog10c(uint64_t v) {
  static const uint64_t thr[64] = {
    10000000000000000000ULL, 0, 0, 0, 1000000000000000000ULL, 0, 0, 100000000000000000ULL, 0, 0,
       10000000000000000ULL, 0, 0, 0,    1000000000000000ULL, 0, 0,    100000000000000ULL, 0, 0,
          10000000000000ULL, 0, 0, 0,       1000000000000ULL, 0, 0,       100000000000ULL, 0, 0,
             10000000000ULL, 0, 0, 0,          1000000000ULL, 0, 0,          100000000ULL, 0, 0,
                10000000ULL, 0, 0, 0,             1000000ULL, 0, 0,             100000ULL, 0, 0,
                   10000ULL, 0, 0, 0,                1000ULL, 0, 0,                100ULL, 0, 0,
                      10ULL, 0, 0, 0
  };
  uint32_t lz = __builtin_clzll(v);
  return (63 - lz) * 3 / 10 + (v >= thr[lz]);
}

Umm, according to this code, ilog10c(1) is 1. ilog10c(7) is 1, and ilog10c(10) is also 1, but ilog10c(8) and ilog10c(9) are zero. The problem is that for all the zero elements in your table, the "v >= thr[lz]" line is adding one and it shouldn't.

This appears to fix it:

return (63 - lz) * 3 / 10 + (thr[lz] && v >= thr[lz]);

Or faster would be just to change all the "0" entries to "-1ULL".

Might I suggest some test code? If the routine was declared constexpr, you could add some static_asserts and not even need a separate file.

static_assert(ilog10c(1) == 0, "");
static_assert(ilog10c(7) == 0, "");
static_assert(ilog10c(9) == 0, "");
static_assert(ilog10c(10) == 1, "");
static_assert(ilog10c(11) == 1, "1");
static_assert(ilog10c(9223372036854775807ULL) == 18, ""); // 2^63-1
static_assert(ilog10c(9223372036854775808ULL) == 18, ""); // 2^63
static_assert(ilog10c(9999999999999999999ULL) == 18, "");
static_assert(ilog10c(10000000000000000000ULL) == 19, "");
static_assert(ilog10c(18446744073709551615ULL) == 19, ""); // 2^64

Also, you can get much better code if your divisor is a power of two, so instead of "3 / 10", use "77 / 256".

See https://godbolt.org/g/1bLGdy for generated code.