3

32ビットの符号なし整数を想定します（もちろん、任意のサイズに一般化できる回答の方が優れています）。

この整数は2の累乗であると見なすことができるため、1ビットのみが設定されます。設定したビットより下のビットを除いて、すべてのビットを整数に設定したいと思います。したがって（簡潔にするために8ビット整数を使用）00001000はになり11111000ます。

もちろん、これは、1つのセットビットを見つけて、上位ビットを反復処理し、それらも設定することで実現できます。highest_set最上位のセットビットの位置を返すと仮定します。

uint32_t f(uint32_t x)
{
  int n = highest_set(x);
  for (int i = 31; i != n; --i) {
      x |= 1 << i;
  }
  return x;
}

ただし、の実行時間はfの値に依存しますx。これを行うには、より賢い方法があると思います。

4

4 に答える 4

5

概念的には、簡単に実行できるのはx-1、それを取得してからとXORすること0xffffffffです。~(x-1)以下のコメントでharoldが行ったようにそれを書くと、 XORを実行しているものを変更することなく、さまざまなサイズの整数を処理できます。

于 2012-09-13T17:29:29.353 に答える
2

右にシフトするlog（value）、またはビットマスクが1の場合は、左にシフトするlog（value）。これは、どの入力に対しても同じ実行時間の一般的なソリューションであるはずですが、保証はありません。

于 2012-09-13T17:40:34.380 に答える
0 
uint32_t f(uint32_t x)
{
  bool bitset=false; //C++
  for (int i =0; i<sizeof(int); i++) {
     if(bitset) //After the first 1
        {  x |= 1 << i; } 
      else
        {
          if(x&(1<<i))
            bitset=true; //if 1 found then the flag is raised
        }

  }
  return x;
}
于 2012-09-13T17:33:11.573 に答える
0

2の補数を取る必要があります

x = -x;

xが符号付きか符号なしかに関係なく機能します

なんで？なぜなら、あなたがしていることは、本質的に、数値を2の補数に変換する簡単な方法だからです。

2進数を2の補数に手動で変換するショートカットは、最下位ビット（LSB）から開始し、最初の1に達するまですべてのゼロ（LSBから最上位ビットに向かって）をコピーすることです。次に、その1をコピーし、残りのすべてのビットを反転します

https://en.wikipedia.org/wiki/Two%27s_complement#Working_from_LSB_towards_MSB

設定されているビットは1つだけなので、すべてのゼロビットをコピーして残りのゼロビットを反転すると、2の補数が得られます。あなたはあなたの例でそれを見ることができます：00001000 = 8, 11111000 = -8。他のいくつかの例：

00010000 = 16, 11110000 = -16
00100000 = 32, 11100000 = -32
01000000 = 64, 11000000 = -64

xが符号付きタイプの場合、理解しやすいです。符号なしタイプの場合、明らかに負の値はないため、C標準が符号なし操作を定義した方法に基づいて機能します。

結果の符号なし整数型で表現できない結果は、結果の型で表現できる最大値より1大きい数を法として減少するため、符号なしオペランドを含む計算はオーバーフローすることはありません。

これは、2の補数の別の定義です。これは、結果の型（つまり、この場合）で表すことができる最大値よりも大きい値が2Nであるためです。符号なしの値を否定すると、符号付きの型が符号の大きさまたは1の補数である場合でも、常にCで2の補数が生成されます。UINTN_MAX + 1

もちろん、x = -(int32_t)x;もっと入力したい場合は、署名付きタイプにキャストすることもできます。別の解決策もあります

x = ~x + 1; // by 2's complement definition

わかりやすいソリューション_

while (!(x & 0x80000000))
    x |= x << 1;

このコードは、上記のソリューションの多くの場合、常に32回ループする必要はありません。

于 2013-08-01T03:58:34.223 に答える