整数版 log2

「与えられている整数値に対するビット幅」を知りたいことは、しばしばあるのですが、C/C++ では標準的な関数として定義されていないようです。（知らないだけかも）

数式にすると $B = \lfloor log_2 N \rfloor$ ですが、欲しい機能は ((int)std::log2(N)) 相当の

log2u.c

int log2u(unsigned int N)
{
  int B = -1;
  while (N != 0)
    {
      ++B;
      N /= 2;
    }
  return B;
}

です。関数名が log2 だと、標準の
　　double std::log2(Integral x);
と区別がつかなくなるので log2u としました。

$N$ が 0 のときは、$-\infty$ の代わりの INT_MIN よりも -1 の方が都合がよいでしょう。

近年(?)の CPU では該当する機能（BSR/CLZ など）が実装されていることが殆どなので、コンパイラの拡張機能を使って高速化できます。

log2u.h

#pragma once
#if defined(_MSC_VER)
#include <intrin.h>
#endif

#if defined(__i386__) || defined(__x86__) || defined(__x86_64__) || defined(__amd64__)

// GCC: x86
inline int log2u(unsigned int x)
{
  int n = -1;
  asm("bsrl %1,%0" : "+r" (n) : "r" (x));
  return n;
}

#elif defined(__arm__)

// GCC: ARM
inline int log2u(unsigned int x)
{
  return (31 - __builtin_clz(x));
}

#elif defined(_M_IX86) || defined(_M_X64) || defined(_M_AMD64)

// VC: x86
inline int log2u(unsigned int x)
{
  unsigned long n;
  _BitScanReverse(&n, x);
  return ((x == 0) ? -1 : (int)n);
}

#elif defined(_M_ARM)

// VC: ARM
inline int log2u(unsigned int x)
{
  return (31 - _arm_clz(x));
}

#else

// other
inline int log2u(unsigned int x)
{
  int r = -1;
  while (x != 0)
    {
      ++r;
      x /= 2;
    }
  return r;
}

#endif

注意： Intel と AMD で違う(?) BSF/BSR 命令

---

log2u.c のコンパイル結果

GCC x86 のアセンブリ出力では、ループ処理が BSR で最適化

Apple clang version 11.0.0 (clang-1100.0.33.17)
Target: x86_64-apple-darwin19.3.0

    .section    __TEXT,__text,regular,pure_instructions
    .build_version macos, 10, 15    sdk_version 10, 15
    .globl  _log2u                  ## -- Begin function log2u
    .p2align    4, 0x90
_log2u:                                 ## @log2u
    .cfi_startproc
## %bb.0:
    pushq   %rbp
    .cfi_def_cfa_offset 16
    .cfi_offset %rbp, -16
    movq    %rsp, %rbp
    .cfi_def_cfa_register %rbp
    testl   %edi, %edi
    je  LBB0_1
## %bb.2:
    bsrl    %edi, %eax
    popq    %rbp
    retq
LBB0_1:
    movl    $-1, %eax
    popq    %rbp
    retq
    .cfi_endproc
                                        ## -- End function

.subsections_via_symbols

GCC ARM のアセンブリ出力では、ループ処理が CLZ にならず

gcc version 8.3.0 (Raspbian 8.3.0-6+rpi1)
Target: arm-linux-gnueabihf

        .arch armv6
        .eabi_attribute 28, 1
        .eabi_attribute 20, 1
        .eabi_attribute 21, 1
        .eabi_attribute 23, 3
        .eabi_attribute 24, 1
        .eabi_attribute 25, 1
        .eabi_attribute 26, 2
        .eabi_attribute 30, 2
        .eabi_attribute 34, 1
        .eabi_attribute 18, 4
        .file   "log2u_base.c"
        .text
        .align  2
        .global log2u
        .arch armv6
        .syntax unified
        .arm
        .fpu vfp
        .type   log2u, %function
log2u:
        @ args = 0, pretend = 0, frame = 0
        @ frame_needed = 0, uses_anonymous_args = 0
        @ link register save eliminated.
        subs    r3, r0, #0
        mvn     r0, #0
        bxeq    lr
.L3:
        lsrs    r3, r3, #1
        add     r0, r0, #1
        bne     .L3
        bx      lr
        .size   log2u, .-log2u
        .ident  "GCC: (Raspbian 8.3.0-6+rpi1) 8.3.0"
        .section        .note.GNU-stack,"",%progbits

VC x86 のアセンブリ出力では、ループ処理が BSR にならず

アセンブリ出力から抜粋

_TEXT   SEGMENT
?log2u@@YAHI@Z PROC                                     ; log2u, COMDAT
        or      eax, -1
        test    ecx, ecx
        je      SHORT $LN3@log2u
$LL2@log2u:
        inc     eax
        shr     ecx, 1
        jne     SHORT $LL2@log2u
$LN3@log2u:
        ret     0
?log2u@@YAHI@Z ENDP                                     ; log2u
_TEXT   ENDS