2017年2月13日

すばらしいビット

まとめ

awesome-bits

by Keon Kim

本記事は、原著者の許諾のもとに翻訳・掲載しております。

精選したビット演算の一覧および技です。
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;

最大値整数（long）の取得

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

2のn乗

2 << (n-1);

2の累乗であるか確認

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

mの2のn乗の剰余

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 に対応します。