位运算有问题

Question

位运算有问题

c++c64-bitbit-manipulation

5

好的，各位，我知道我想要做什么，但我不知道它是否已经存在（作为函数或理论）或如何描述它，所以我需要你们的帮助：

假设我们有一个二进制数：（最高有效位）10101110（最低有效位）
从第X位开始，一旦遇到第一个零位，我就想将所有其他位（向左移位）清零。
尽可能快地完成，使用必需的最少数量操作和CPU周期

举个例子：

数字=10101110，起始位置=1（第1位的位=1）
position++-第2位的位=1，继续
position++-第3位的位=1，继续
position++-第4位的位=0，糟糕…遇到了零…现在，所有位都必须归零。

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

有什么想法吗？

- Dr.Kameleon

@MitchWheat 相信我，我已经涵盖了整个笔记本的草图，用于各种极端位图操作。问题是，我所能想到的这一个包括一个循环（我绝对希望避免）。 - Dr.Kameleon

@MitchWheat 他说这可能不是最快的方法。我同意他的观点。 - Mysticial

@MitchWheat 这将会被执行数百万次，所以肯定会影响速度，这就是为什么。 - Dr.Kameleon

@MitchWheat 每秒钟。（以及其他十几个计算） :-) - Dr.Kameleon

1

@MitchWheat 好的，没必要保密：这是我为我的一个国际象棋引擎项目编写的移动生成算法的一部分。所以，如果你曾经使用过国际象棋编程和位图，你就知道我在说什么了...;-) - Dr.Kameleon

4个回答

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

- rici

我有点作弊，只读了一半的问题就回答了你...;-) - R.. GitHub STOP HELPING ICE

对于 x=10101110 和 POS=1，这将返回 10100000（实际上是相反的）。 - Dr.Kameleon

好的，我刚刚重新测试了一下。我确认：它可以工作。我猜我得运行一些分析测试来看哪个版本运行更快...非常感谢你的所有努力！ :-) - Dr.Kameleon

@Dr.Kameleon：我使用pos=2和pos=31对所有32位整数（因此总共有2^34个调用，每个函数2^33个）进行了比较，以进行健全性检查。预计需要17秒钟，大致均分在两者之间。因此，那大约是每秒十亿（内联）函数调用。这对您来说应该足够快了，不是吗？ - rici

1

CROPLEFT(int X,int POS) {

    int mask = 1 << POS;

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

    return (X & (mask - 1));
}

- Adeel Ahmed

这与我自己编写的代码几乎完全相同，但由于那个循环问题，我决定避免使用。不管怎样，非常感谢你，伙计... :-) - Dr.Kameleon

0

将末尾的零替换为一：

x = x | (x-1);

将末尾的1替换为0：

x = x & (x+1);

编辑：哎呀，看起来我读错了问题，上面的代码将右边的位清零，而不是左边的位！

要将左边的位清零，我们需要进行最后一次异或操作：

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

- aka.nice

自从昨天我得到了检查器，我也检查了你的。它可以工作 :) 它有十个指令，比我的多一个但比@R的少两个。 - rici

@rici 我们的代码几乎相同，我额外增加的步骤可能是对问题的错误解释，因为我忽略了在 POS 上遇到的第一组零。 - aka.nice

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- R.. GitHub STOP HELPING ICE · Accepted Answer

小菜一碟。

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指令，那么获取最高设置位就没有这样的运气，所以您很幸运您的问题需要最低设置位。