VC中实现RadixTree中获取0数量的位运算函数

GCC中内嵌了两个位运算的函数,但在VC中并没有这两个函数(有相似函数)。

//返回前导的0的个数。
int __builtin_clz (unsigned int x)
//返回后面的0个个数,和__builtin_clz相对。
int __builtin_ctz (unsigned int x)

这两个函数在radix tree中直接计算索引,对性能有一定要求。

自己写有些效率问题不是很理想,所以想确定vc2015 版本中是否有带已经优化过的函数。在网上兜了一圈,没有找到类似VC实现的代码。折腾了半天没找到解决方案,后来到CSDN上发了个贴解决问题。

VC相似函数

_BitScanForward()
https://msdn.microsoft.com/en-us/library/wfd9z0bb.aspx
_BitScanReverse()
https://msdn.microsoft.com/en-us/library/fbxyd7zd.aspx

有64位版本的处理,需要处理一下就和GCC中得到相同结果

基本原理

  • 正向扫描指令BSF(BitScan Forward)从右向左扫描,即:从低位向高位扫描;
  • 逆向扫描指令BSR(BitScan Reverse)从左向右扫描,即:从高位向低位扫描。

处理方法

下面简单实现这两个函数。把这两个测试代码贴出来供遇到同样问题的人提帮助。

输出的值和GCC版本是一致的,可直接使用。

vc test code(32位)

// ConsoleApplication1.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include <bitset>

using namespace std;

__inline int __builtin_clz(int v) {
    if (v == 0)
        return 31;

    __asm
    {
        bsr ecx, dword ptr[v];
        mov eax, 1Fh;
        sub eax, ecx;
    }
}

__inline int __builtin_ctz(int v) 
{
    int pos;
    if (v == 0)
        return 0;

    __asm
    {
        bsf eax, dword ptr[v];
    }
}

int main()
{
    // clz
    printf("__builtin_clz:\n");
    for (int i = 0; i < 32; i++) {
        int v = 1 << i;
        bitset<32> b(v);
        printf("%12u(%s): %2d  %s \n", 
               v, b.to_string().c_str(), 
               __builtin_clz(v), __builtin_clz(v) == 31 - i ? "OK" : "Err");
    }
    printf("\n");

    // ctz
    printf("__builtin_ctz:\n");
    for (int i = 0; i < 32; i++) {
        int v = 1 << i;
        bitset<32> b(v);
        printf("%12u(%s): %2d  %s \n", 
               v, b.to_string().c_str(), 
               __builtin_ctz(v), __builtin_ctz(v) == i ? "OK" : "Err");
    }

    return 0;
}