2017年2月13日

すばらしいビット

精選したビット演算の一覧および技です。
Keon Kimが管理しています。お気軽にプルリクエストを送ってください。

整数

n乗ビットの設定

x | (1<<n)

n乗ビットの解除

x & ~(1<<n)

n乗ビットのトグル

x ^ (1<<n)

2の累乗に切り上げ

unsigned int v; //only works if v is 32 bit
v--;
v |= v >> 1;
v |= v >> 2;
v |= v >> 4;
v |= v >> 8;
v |= v >> 16;
v++;

最大整数の取得

int maxInt = ~(1 << 31);
int maxInt = (1 << 31) - 1;
int maxInt = (1 << -1) - 1;

最小整数の取得

int minInt = 1 << 31;
int minInt = 1 << -1;

最大値整数（64ビット）の取得

long maxLong = ((long)1 << 127) - 1;

2を掛ける

n << 1; // n*2

2で割る

n >> 1; // n/2

2のm乗を掛ける

n << m;

2のm乗で割る

n >> m;

等しいことを確認

JavaScriptよりも35%処速が速くなります。

(a^b) == 0; // a == b
!(a^b) // use in an if

値が奇数であることを確認

(n & 1) == 1;

2つの値を交換（スワップ）

//version 1
a ^= b;
b ^= a;
a ^= b;

//version 2
a = a ^ b ^ (b = a)

絶対値の取得

//version 1
x < 0 ? -x : x;

//version 2
(x ^ (x >> 31)) - (x >> 31);

2つの値の最大値を取得

b & ((a-b) >> 31) | a & (~(a-b) >> 31);

2つの値の最小値を取得

a & ((a-b) >> 31) | b & (~(a-b) >> 31);

2つの値が同じ記号であることを確認

(x ^ y) >= 0;

記号の反転

i = ~i + 1; // or
i = (i ^ -1) + 1; // i = -i

2nの計算

2 << (n-1);

2の累乗であるか確認

n > 0 && (n & (n - 1)) == 0;

mの2n剰余

m & (n - 1);

平均値の取得

(x + y) >> 1;
((x ^ y) >> 1) + (x & y);

nのm乗ビットの取得(昇順)

(n >> (m-1)) & 1;

nのm乗ビットを0に設定(昇順)

n & ~(1 << (m-1));

n乗ビットが設定されていることを確認

if (x & (1<<n)) {
  n-th bit is set
} else {
  n-th bit is not set
}

最右の1ビットを分離(抽出)

x & (-x)

最右の0ビットを分離(抽出)

~x & (x+1)

最右ビットを0から1に設定

x | (x+1)

n + 1

-~n

n – 1

~-n

負の値を取得する

~n + 1;
(n ^ -1) + 1;

if (x == a) x = b; if (x == b) x = a;

x = a ^ b ^ x;

隣接するビットをスワップ

((n & 10101010) >> 1) | ((n & 01010101) << 1)

m値とn値の異なる最右ビット

(n^m)&-(n^m) // returns 2^x where x is the position of the differnet bit (0 based)

m値とn値の共通する最右ビット

~(n^m)&(n^m)+1 // returns 2^x where x is the position of the common bit (0 based)

浮動小数点

下記に挙げるのは、平方根の逆数を高速で求める方法に触発されてできた手法です。これらのほとんどは独自の手法です。

浮動小数点をビット配列に変換（unsigned uint32_t）

#include <stdint.h>
typedef union {float flt; uint32_t bits} lens_t;
uint32_t f2i(float x) {
  return ((lens_t) {.flt = x}).bits;
}

注意：共用体を介した型のプルーニングはC++で定義されていませんので、代わりにstd::memcpyを使ってください。

ビット配列を浮動小数点に戻す

float i2f(uint32_t x) {
  return ((lens_t) {.bits = x}).flt;
}

`frexp`を使用して正の浮動小数点のビット配列の近似値を求める

frexpは値を2のn乗で分解するため、man, exp = frexp(x)はman * 2exp = x and 0.5 <= man < 1になります。

man, exp = frexp(x);
return (uint32_t)((2 * man + exp + 125) * 0x800000);

注意：frexpを使用するとman+125によって最後の8ビットを上書きして仮数の最初の16ビットを格納するため、最大2から16の相対誤差を持ちます。

高速な平方根の逆数

return i2f(0x5f3759df - f2i(x) / 2);

注意：代わりに上記のi2f関数と2i関数を使用しています。

Wikipediaの記載を参照してください。

無限級数による正数の高速なn乗根

float root(float x, int n) {
#DEFINE MAN_MASK 0x7fffff
#DEFINE EXP_MASK 0x7f800000
#DEFINE EXP_BIAS 0x3f800000
  uint32_t bits = f2i(x);
  uint32_t man = bits & MAN_MASK;
  uint32_t exp = (bits & EXP_MASK) - EXP_BIAS;
  return i2f((man + man / n) | ((EXP_BIAS + exp / n) & EXP_MASK));
}

導出については、こちらのブログ記事をご覧ください。

高速な任意の累乗

return i2f((1 - exp) * (0x3f800000 - 0x5c416) + f2i(x) * exp)

注意：0x5c416のバイアスはこの方法を用いるために設定されたものです。exp = -0.5を代入する場合、このバイアスは平方根の逆数を高速で求める方法の定和である0x5f3759dfになります。

この方法の導出についてはこちらの一連のスライドをご覧ください。

高速な幾何平均

一連のnの数値の幾何平均はそれらの積のn乗根です。

#include <stddef.h>
float geometric_mean(float* list, size_t length) {
  // Effectively, find the average of map(f2i, list)
  uint32_t accumulator = 0;
  for (size_t i = 0; i < length; i++) {
    accumulator += f2i(list[i]);
  }
  return i2f(accumulator / n);
}

導出についてはこちらをご覧ください。

高速な自然対数

#DEFINE EPSILON 1.1920928955078125e-07
#DEFINE LOG2 0.6931471805599453
return (f2i(x) - (0x3f800000 - 0x66774)) * EPSILON * LOG2

注意：0x66774のバイアス項はこの方法を用いるために設定されたものです。最後にln(2)を掛けているのは、この方法のその他の部分でlog2(x)関数を計算しているためです。

導出はこちらをご覧ください。

高速な自然指数

return i2f(0x3f800000 + (uint32_t)(x * (0x800000 + 0x38aa22)))

注意：ここでの0x38aa22のバイアス項は、基数の乗法スケールに対応します。特に、2Z= eのようなZに対応します。