3

整数のバイナリ表現でゼロ以外の最初の数字の後のすべての数字を切り捨てたいと思います。また、これをできるだけ単純にする必要があります (関数や複数行のコードはありません)。

例:

// in c++
int int1=7,int2=12,int3=34;   //needs to work for any number

ある種の演算子 (おそらくビットごとの組み合わせ?) を使用して、次の値を与えるためにこれらが必要です

int1 -> 4
int2 -> 8
int3 -> 32

バイナリでの切り捨てしか考えられなかったので、どんなアイデアでも受け入れます。

ありがとう！

4

2 に答える 2

3

そのためには、かなり巧妙なトリックを使用できます。

if ((v & (v - 1)) == 0) {
    return v;
}
v--;
v |= v >> 1;
v |= v >> 2;
v |= v >> 4;
v |= v >> 8;
v |= v >> 16;
v++;
v >>= 1;
return v;

アイデアはOR、値をデクリメントした後、一番上のものより下のすべてのものを「イン」し、最後に値をインクリメントすることです。2^n元のコードは、指定された値以上の最小値を見つけるように設計されていたため、標準のトリックの最後に右シフトを追加しました。

編集:の特別なケースも追加しました2^N。これは、同じリストの別のトリックです。

これはideoneのデモです。

于 2013-07-22T01:08:35.773 に答える
3

この関数は本からのものHacker's Delightです。

// greatest power of 2 less than or equal to n (floor pow2)

uint32_t flp2(uint32_t n)
{
    n |= n >> 1;
    n |= n >> 2;
    n |= n >> 4;
    n |= n >> 8;
    n |= n >> 16;
    return n - (n >> 1);
}

そして、関連するclp2関数を投稿することもできます：

// least power of 2 greater than or equal to n (ceiling pow2)

uint32_t clp2(uint32_t n)
{
    n -= 1; 
    n |= n >> 1;
    n |= n >> 2;
    n |= n >> 4;
    n |= n >> 8;
    n |= n >> 16;
    return n + 1;
}
于 2013-07-22T01:20:33.307 に答える