5

好的，伙计们，我知道我想做什么，但我不知道它是否已经存在（作为一个函数或理论上）或者如何表达它，所以我需要你的帮助：

  • 假设我们有一个二进制数：(msb) 10101110(lsb)
  • 从位 X 开始，我想在遇到第一个零位时将所有其他位清零（向左）。
  • 尽可能快地做到这一点，所需的操作和 CPU 周期绝对最少

一个例子 ：

  • 数字 = 10101110，起始位置 = 1（位置 1 的位 = 1）
  • position++ - 位置 2 = 1，继续
  • position++ - 位置 3 = 1，继续
  • position++ - 位置 4 = 0 的位，哎呀……遇到零……现在，一切都必须归零。

因此，我们想象的函数 CROPLEFT(X,POS) 的最终结果，其中 X=10101110 和 POS=1，将返回00001110。

有任何想法吗？

4

4 回答 4

12

小菜一碟。

y = ~x;    // We like working with 1's, not 0's.
y &= -y;   // Mask off all but the lowest-set bit
x &= y-1;  // Make a mask for the bits below that and apply it.

并添加了位置参数：

y = ~x & -1U<<pos; // Change 1U to a larger type if needed.
y &= -y;
x &= y-1;

关键要素是第二行，并且您可以y通过应用逻辑和反对来仅用其最低设置位替换一个值-y。遗憾的是，获得最高设置位没有这样的运气，除非您有一个特殊的 cpu 指令，所以您很幸运，您的问题要求最低。

于 2012-12-15T05:18:07.510 回答
3

好吧，什么鬼：

return x & ((x ^ (x + (1UL << POS))) | ((1UL << POS) - 1))

值得一提的是，它们都是用 gcc-4.7 -O3 编译的。R..在左边，我在右边：（在他们两个中都使用 unsigned long 和 1UL）

        .p2align 4,,15                          .p2align 4,,15
        .globl  zapleft                         .globl  zapleft2
        .type   zapleft, @function              .type   zapleft2, @function
zapleft:                                zapleft2:           
.LFB0:                                  .LFB1:
        .cfi_startproc                          .cfi_startproc
        movl    %esi, %ecx                      movl    %esi, %ecx
        movq    %rdi, %rax                      movl    $1, %edx
        movq    $-1, %rdx                       salq    %cl, %rdx
        salq    %cl, %rdx                       leaq    (%rdx,%rdi), %rax
        notq    %rax                            subq    $1, %rdx
        andq    %rax, %rdx                      xorq    %rdi, %rax
        movq    %rdx, %rax                      orq     %rdx, %rax
        negq    %rax                            andq    %rdi, %rax
        andq    %rdx, %rax                      ret
        subq    $1, %rax                        .cfi_endproc
        andq    %rdi, %rax              .LFE1:
        ret                             .size   zapleft2, .-zapleft2
        .cfi_endproc
.LFE0:
        .size   zapleft, .-zapleft
于 2012-12-15T05:27:33.833 回答
1 
CROPLEFT(int X,int POS) {

    int mask = 1 << POS;

    while (X & mask)
        mask <<= 1;

    return (X & (mask - 1));
}
于 2012-12-15T05:28:59.597 回答
0

用一个替换尾随零：

x = x | (x-1);

用零替换尾随的：

x = x & (x+1);

编辑：哎呀，看来我误读了这个问题，上面的代码将右侧位归零，而不是左侧位！

要将左边的位归零，我们需要一个最终的 XOR 操作：

y = x | (x-1);
y = y & (y+1);
y = x ^ y;

编辑 2关于起始位置 POS

我们只需在第一步中将最右边的 POS 位清零。

y = x & (-1U<<pos);
y = y | (y-1);
y = y & (y+1);
y = x ^ y;

编辑 3如果在 POS 遇到第一组零，则上述解决方案将忽略它们。
如果这不能回答问题，那么代码会更短，但很像现在的 rci ：

y = x | ((1U<<pos)-1); // fill trailing positions with ones
y = y & (y+1);         // replace trailing ones by zeroes
y = x ^ y;             // modify leading bits rather than trailing ones
于 2012-12-15T11:27:26.273 回答