5

OK、皆さん、やりたいことはわかっていますが、それが(関数として、または理論的に)既に存在するかどうか、またはそれを表現する方法がわからないので、あなたの助けが必要です:

  • 2 進数があるとしましょう: (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重要な要素は 2 行目であり、 logical and against を適用することで、値をその最下位ビットに置き換えることができるという事実です-y。悲しいことに、特別な CPU 命令がない限り、最高のビットを取得する幸運はありません。

于 2012-12-15T05:18:07.510 に答える
3

OK、一体何だ：

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

末尾のゼロを 1 に置き換えます。

x = x | (x-1);

末尾の 1 をゼロに置き換えます。

x = x & (x+1);

編集：おっと、質問を読み間違えたようです。上記のコードは、左のビットではなく右のビットをゼロにします!

左のビットをゼロにするには、最終的な XOR 演算が必要です。

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

EDIT 2開始位置 POS について

最初のステップで最も右側の POS ビットをゼロにするだけです。

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

EDIT 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 に答える