设置的最低有效位的位置

Question

我正在寻找一种有效的方法来确定在整数中设置的最低有效位的位置,例如对于0x0FF0,它将是4.

这是一个简单的实现:

unsigned GetLowestBitPos(unsigned value)
{
   assert(value != 0); // handled separately

   unsigned pos = 0;
   while (!(value & 1))
   {
      value >>= 1;
      ++pos;
   }
   return pos;
}

任何想法如何挤出一些周期？

(注意:这个问题适合喜欢这类事情的人,而不是人们告诉我xyzoptimization是邪恶的.)

[编辑] 感谢大家的想法!我也学到了其他一些东西.凉!

Answer 1

Bit Twiddling Hacks提供了一系列精彩的,呃,有点笨拙的黑客,并附有性能/优化讨论.我最喜欢的问题解决方案(来自该网站)是«乘法和查找»:

unsigned int v;  // find the number of trailing zeros in 32-bit v 
int r;           // result goes here
static const int MultiplyDeBruijnBitPosition[32] = 
{
  0, 1, 28, 2, 29, 14, 24, 3, 30, 22, 20, 15, 25, 17, 4, 8, 
  31, 27, 13, 23, 21, 19, 16, 7, 26, 12, 18, 6, 11, 5, 10, 9
};
r = MultiplyDeBruijnBitPosition[((uint32_t)((v & -v) * 0x077CB531U)) >> 27];

有用的参考:

• " 使用de Bruijn序列在计算机词中索引1 " - 解释为什么上述代码有效.
• " Board Representation> Bitboards> BitScan " - 详细分析这个问题,特别关注国际象棋编程

Answer 2

为什么不使用内置的ffs？(我从Linux手中获取了一个手册页,但它比这更广泛.)

ffs(3) - Linux手册页

名称

ffs - 查找单词中的第一个位

概要

#include <strings.h>
int ffs(int i);
#define _GNU_SOURCE
#include <string.h>
int ffsl(long int i);
int ffsll(long long int i);

描述

ffs()函数返回单词i中设置的第一个(最低有效)位的位置.最低有效位是位置1和最高有效位置,例如32或64.函数ffsll()和ffsl()执行相同但接受可能不同大小的参数.

回报价值

这些函数返回第一个位集的位置,如果i中没有设置位,则返回0.

符合

4.3BSD,POSIX.1-2001.

笔记

BSD系统有一个原型<string.h>.

Answer 3

有一个x86汇编指令(bsf)可以执行它.:)

更优化？!

边注:

此级别的优化本质上取决于架构.今天的处理器过于复杂(在分支预测,缓存未命中,流水线方面),很难预测哪个代码在哪个架构上执行得更快.将操作从32减少到9或类似的事情甚至可能会降低某些体系结构的性能.单个体系结构上的优化代码可能会导致另一个体系结构中的代码更糟糕.我想你要么为特定的CPU优化它,要么保持原样,让编译器选择它认为更好的东西.

Answer 4

大多数现代架构都会有一些指令来查找最低设置位的位置,或最高设置位,或计算前导零的数量等.

如果你有这个课程的任何一个指令,你可以便宜地模仿其他人.

花一点时间在纸上完成它并意识到x & (x-1)它将清除x中的最低设置位,并且( x & ~(x-1) )将返回最低设置位,而不管结构,字长等.知道这一点,使用硬件计数领先是微不足道的-zeroes/maximum-set-bit如果没有明确的指令,则找到最低设置位.

如果根本没有相关的硬件支持,那么这里给出的count-leading- zero的乘法和查找实现或Bit Twiddling Hacks页面上的其中一个可以使用上述标识轻松转换为最低设置位具有无分支的优点.

Answer 5

Weee,大量的解决方案,而不是一个基准.你们应该为自己感到羞耻;-)

我的机器是Intel i530(2.9 GHz),运行Windows 7 64位.我用32位版本的MinGW编译.

$ gcc --version
gcc.exe (GCC) 4.7.2

$ gcc bench.c -o bench.exe -std=c99 -Wall -O2
$ bench
Naive loop.         Time = 2.91  (Original questioner)
De Bruijn multiply. Time = 1.16  (Tykhyy)
Lookup table.       Time = 0.36  (Andrew Grant)
FFS instruction.    Time = 0.90  (ephemient)
Branch free mask.   Time = 3.48  (Dan / Jim Balter)
Double hack.        Time = 3.41  (DocMax)

$ gcc bench.c -o bench.exe -std=c99 -Wall -O2 -march=native
$ bench
Naive loop.         Time = 2.92
De Bruijn multiply. Time = 0.47
Lookup table.       Time = 0.35
FFS instruction.    Time = 0.68
Branch free mask.   Time = 3.49
Double hack.        Time = 0.92

我的代码:

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


#define ARRAY_SIZE 65536
#define NUM_ITERS 5000  // Number of times to process array


int find_first_bits_naive_loop(unsigned nums[ARRAY_SIZE])
{
    int total = 0; // Prevent compiler from optimizing out the code
    for (int j = 0; j < NUM_ITERS; j++) {
        for (int i = 0; i < ARRAY_SIZE; i++) {
            unsigned value = nums[i];
            if (value == 0)
                continue;
            unsigned pos = 0;
            while (!(value & 1))
            {
                value >>= 1;
                ++pos;
            }
            total += pos + 1;
        }
    }

    return total;
}


int find_first_bits_de_bruijn(unsigned nums[ARRAY_SIZE])
{
    static const int MultiplyDeBruijnBitPosition[32] = 
    {
       1, 2, 29, 3, 30, 15, 25, 4, 31, 23, 21, 16, 26, 18, 5, 9, 
       32, 28, 14, 24, 22, 20, 17, 8, 27, 13, 19, 7, 12, 6, 11, 10
    };

    int total = 0; // Prevent compiler from optimizing out the code
    for (int j = 0; j < NUM_ITERS; j++) {
        for (int i = 0; i < ARRAY_SIZE; i++) {
            unsigned int c = nums[i];
            total += MultiplyDeBruijnBitPosition[((unsigned)((c & -c) * 0x077CB531U)) >> 27];
        }
    }

    return total;
}


unsigned char lowestBitTable[256];
int get_lowest_set_bit(unsigned num) {
    unsigned mask = 1;
    for (int cnt = 1; cnt <= 32; cnt++, mask <<= 1) {
        if (num & mask) {
            return cnt;
        }
    }

    return 0;
}
int find_first_bits_lookup_table(unsigned nums[ARRAY_SIZE])
{
    int total = 0; // Prevent compiler from optimizing out the code
    for (int j = 0; j < NUM_ITERS; j++) {
        for (int i = 0; i < ARRAY_SIZE; i++) {
            unsigned int value = nums[i];
            // note that order to check indices will depend whether you are on a big 
            // or little endian machine. This is for little-endian
            unsigned char *bytes = (unsigned char *)&value;
            if (bytes[0])
                total += lowestBitTable[bytes[0]];
            else if (bytes[1])
              total += lowestBitTable[bytes[1]] + 8;
            else if (bytes[2])
              total += lowestBitTable[bytes[2]] + 16;
            else
              total += lowestBitTable[bytes[3]] + 24;
        }
    }

    return total;
}


int find_first_bits_ffs_instruction(unsigned nums[ARRAY_SIZE])
{
    int total = 0; // Prevent compiler from optimizing out the code
    for (int j = 0; j < NUM_ITERS; j++) {
        for (int i = 0; i < ARRAY_SIZE; i++) {
            total +=  __builtin_ffs(nums[i]);
        }
    }

    return total;
}


int find_first_bits_branch_free_mask(unsigned nums[ARRAY_SIZE])
{
    int total = 0; // Prevent compiler from optimizing out the code
    for (int j = 0; j < NUM_ITERS; j++) {
        for (int i = 0; i < ARRAY_SIZE; i++) {
            unsigned value = nums[i];
            int i16 = !(value & 0xffff) << 4;
            value >>= i16;

            int i8 = !(value & 0xff) << 3;
            value >>= i8;

            int i4 = !(value & 0xf) << 2;
            value >>= i4;

            int i2 = !(value & 0x3) << 1;
            value >>= i2;

            int i1 = !(value & 0x1);

            int i0 = (value >> i1) & 1? 0 : -32;

            total += i16 + i8 + i4 + i2 + i1 + i0 + 1;
        }
    }

    return total;
}


int find_first_bits_double_hack(unsigned nums[ARRAY_SIZE])
{
    int total = 0; // Prevent compiler from optimizing out the code
    for (int j = 0; j < NUM_ITERS; j++) {
        for (int i = 0; i < ARRAY_SIZE; i++) {
            unsigned value = nums[i];
            double d = value ^ (value - !!value); 
            total += (((int*)&d)[1]>>20)-1022; 
        }
    }

    return total;
}


int main() {
    unsigned nums[ARRAY_SIZE];
    for (int i = 0; i < ARRAY_SIZE; i++) {
        nums[i] = rand() + (rand() << 15);
    }

    for (int i = 0; i < 256; i++) {
        lowestBitTable[i] = get_lowest_set_bit(i);
    }


    clock_t start_time, end_time;
    int result;

    start_time = clock();
    result = find_first_bits_naive_loop(nums);
    end_time = clock();
    printf("Naive loop.         Time = %.2f, result = %d\n", 
        (end_time - start_time) / (double)(CLOCKS_PER_SEC), result);

    start_time = clock();
    result = find_first_bits_de_bruijn(nums);
    end_time = clock();
    printf("De Bruijn multiply. Time = %.2f, result = %d\n", 
        (end_time - start_time) / (double)(CLOCKS_PER_SEC), result);

    start_time = clock();
    result = find_first_bits_lookup_table(nums);
    end_time = clock();
    printf("Lookup table.       Time = %.2f, result = %d\n", 
        (end_time - start_time) / (double)(CLOCKS_PER_SEC), result);

    start_time = clock();
    result = find_first_bits_ffs_instruction(nums);
    end_time = clock();
    printf("FFS instruction.    Time = %.2f, result = %d\n", 
        (end_time - start_time) / (double)(CLOCKS_PER_SEC), result);

    start_time = clock();
    result = find_first_bits_branch_free_mask(nums);
    end_time = clock();
    printf("Branch free mask.   Time = %.2f, result = %d\n", 
        (end_time - start_time) / (double)(CLOCKS_PER_SEC), result);

    start_time = clock();
    result = find_first_bits_double_hack(nums);
    end_time = clock();
    printf("Double hack.        Time = %.2f, result = %d\n", 
        (end_time - start_time) / (double)(CLOCKS_PER_SEC), result);
}

Answer 6

最快(非内在/非汇编)解决方案是找到最低字节,然后在256条目查找表中使用该字节.这给出了四个条件指令的最坏情况性能和最佳情况1.这不仅是指令数量最少,而且是现代硬件上最重要的分支数量.

您的表(256个8位条目)应包含0-255范围内每个数字的LSB索引.检查值的每个字节并找到最低的非零字节,然后使用此值查找实际索引.

这确实需要256字节的内存,但如果这个函数的速度如此重要,那么256字节非常值得,

例如

byte lowestBitTable[256] = {
.... // left as an exercise for the reader to generate
};

unsigned GetLowestBitPos(unsigned value)
{
  // note that order to check indices will depend whether you are on a big 
  // or little endian machine. This is for little-endian
  byte* bytes = (byte*)value;
  if (bytes[0])
    return lowestBitTable[bytes[0]];
  else if (bytes[1])
      return lowestBitTable[bytes[1]] + 8;
  else if (bytes[2])
      return lowestBitTable[bytes[2]] + 16;
  else
      return lowestBitTable[bytes[3]] + 24;  
}

Answer 7

OMG只是螺旋式上升.

大多数这些例子缺乏的是对所有硬件如何工作的一点了解.

只要你有一个分支,CPU就必须猜测将采取哪个分支.指令管道加载了引导猜测路径的指令.如果CPU猜错了,则刷新指令管道,并且必须加载另一个分支.

考虑顶部的简单while循环.猜测将保持在循环内.它离开循环时至少会出错一次.这将刷新指令管道.这种行为稍微好于猜测它会离开循环,在这种情况下它会在每次迭代时刷新指令管道.

从一种处理器到下一种处理器,丢失的CPU周期量变化很大.但是你可以预期20到150个CPU周期丢失.

下一个更糟糕的组是您认为通过将值拆分为更小的块并添加更多分支来保存几次迭代的位置.这些分支中的每一个都增加了冲洗指令管道的额外机会,并且花费另外20到150个时钟周期.

让我们考虑一下在表中查找值时会发生什么.有可能当前值不在缓存中,至少不是第一次调用函数.这意味着在从缓存加载值时CPU将停止运行.同样,这也因机器而异.新的英特尔芯片实际上使用它作为交换线程的机会,而当前线程正在等待缓存加载完成.这可能比指令管道刷新更加昂贵,但是如果您多次执行此操作,则可能只发生一次.

显然,最快的恒定时间解决方案是涉及确定性数学的解决方案.一个纯粹而优雅的解决方案

如果这已经被覆盖,我表示歉意.

我使用的每个编译器(XCODE AFAIK除外)都具有前向位扫描和反向位扫描的编译器内在函数.这些将编译为大多数硬件上的单个汇编指令,没有Cache Miss,没有Branch Miss-Prediction,也没有其他程序员生成的绊脚石块.

对于Microsoft编译器,请使用_BitScanForward和_BitScanReverse.
对于GCC,请使用__builtin_ffs,__ builtin_clz,__ builtin_ctz.

此外,如果您对所讨论的主题知之甚少,请不要发布答案并可能误导新人.

对不起,我完全忘了提供解决方案..这是我在IPAD上使用的代码,它没有任务的汇编级指令:

unsigned BitScanLow_BranchFree(unsigned value)
{
    bool bwl = (value & 0x0000ffff) == 0;
    unsigned I1 = (bwl * 15);
    value = (value >> I1) & 0x0000ffff;

    bool bbl = (value & 0x00ff00ff) == 0;
    unsigned I2 = (bbl * 7);
    value = (value >> I2) & 0x00ff00ff;

    bool bnl = (value & 0x0f0f0f0f) == 0;
    unsigned I3 = (bnl * 3);
    value = (value >> I3) & 0x0f0f0f0f;

    bool bsl = (value & 0x33333333) == 0;
    unsigned I4 = (bsl * 1);
    value = (value >> I4) & 0x33333333;

    unsigned result = value + I1 + I2 + I3 + I4 - 1;

    return result;
}

这里要理解的是,这不是比较昂贵的,而是比较后发生的分支.在这种情况下的比较强制为值为0或1,而.. == 0,结果用于组合分支两侧发生的数学运算.

编辑:

上面的代码完全破碎了.此代码有效并且仍然是无分支的(如果已优化):

int BitScanLow_BranchFree(ui value)
{
    int i16 = !(value & 0xffff) << 4;
    value >>= i16;

    int i8 = !(value & 0xff) << 3;
    value >>= i8;

    int i4 = !(value & 0xf) << 2;
    value >>= i4;

    int i2 = !(value & 0x3) << 1;
    value >>= i2;

    int i1 = !(value & 0x1);

    int i0 = (value >> i1) & 1? 0 : -32;

    return i16 + i8 + i4 + i2 + i1 + i0;
}

如果给定为0,则返回-1.如果您不关心0或者很高兴得到31为0,则删除i0计算,节省一大块时间.

Answer 8

受到这篇涉及搜索设置位的类似帖子的启发,我提供以下内容:

unsigned GetLowestBitPos(unsigned value)
{
   double d = value ^ (value - !!value); 
   return (((int*)&d)[1]>>20)-1023; 
}

优点:

• 没有循环
• 没有分支
• 在恒定的时间运行
• 通过返回超出范围的结果来处理value = 0
• 只有两行代码

缺点:

• 假设编码的字节序很少(可以通过改变常数来修复)
• 假设double是真正的*8 IEEE浮点数(IEEE 754)

更新: 正如评论中所指出的,工会是一个更清洁的实现(至少对C来说),看起来像:

unsigned GetLowestBitPos(unsigned value)
{
    union {
        int i[2];
        double d;
    } temp = { .d = value ^ (value - !!value) };
    return (temp.i[1] >> 20) - 1023;
}

假设32位整数用于所有内容的小端存储(想想x86处理器).

Answer 9

最坏的情况是少于32次操作即可完成此操作：

原理：检查2位或更多位与检查1位一样有效。

因此，例如，没有什么可以阻止您先检查哪个分组，然后检查该组中从最小到最大的每个比特。

所以...
如果一次检查2位，则在最坏的情况下为（Nbits / 2）+ 1次检查总数。
如果一次检查3位，则在最坏的情况下为（Nbits / 3）+ 2次检查总数。
...

最佳选择是以4为一组的组，这在最坏的情况下需要11次操作，而不是32次。

最好的情况是从算法的1次检查到2次检查（如果您使用此分组概念）。但是，最好的情况下多花1张支票可节省最坏的情况。

注意：我将其完整写出，而不是使用循环，因为这样做更有效。

int getLowestBitPos(unsigned int value)
{
    //Group 1: Bits 0-3
    if(value&0xf)
    {
        if(value&0x1)
            return 0;
        else if(value&0x2)
            return 1;
        else if(value&0x4)
            return 2;
        else
            return 3;
    }

    //Group 2: Bits 4-7
    if(value&0xf0)
    {
        if(value&0x10)
            return 4;
        else if(value&0x20)
            return 5;
        else if(value&0x40)
            return 6;
        else
            return 7;
    }

    //Group 3: Bits 8-11
    if(value&0xf00)
    {
        if(value&0x100)
            return 8;
        else if(value&0x200)
            return 9;
        else if(value&0x400)
            return 10;
        else
            return 11;
    }

    //Group 4: Bits 12-15
    if(value&0xf000)
    {
        if(value&0x1000)
            return 12;
        else if(value&0x2000)
            return 13;
        else if(value&0x4000)
            return 14;
        else
            return 15;
    }

    //Group 5: Bits 16-19
    if(value&0xf0000)
    {
        if(value&0x10000)
            return 16;
        else if(value&0x20000)
            return 17;
        else if(value&0x40000)
            return 18;
        else
            return 19;
    }

    //Group 6: Bits 20-23
    if(value&0xf00000)
    {
        if(value&0x100000)
            return 20;
        else if(value&0x200000)
            return 21;
        else if(value&0x400000)
            return 22;
        else
            return 23;
    }

    //Group 7: Bits 24-27
    if(value&0xf000000)
    {
        if(value&0x1000000)
            return 24;
        else if(value&0x2000000)
            return 25;
        else if(value&0x4000000)
            return 26;
        else
            return 27;
    }

    //Group 8: Bits 28-31
    if(value&0xf0000000)
    {
        if(value&0x10000000)
            return 28;
        else if(value&0x20000000)
            return 29;
        else if(value&0x40000000)
            return 30;
        else
            return 31;
    }

    return -1;
}

Answer 10

11 年后，我们终于有了：countr_zero

干得好 C++20