すばらしいビット

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

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

文字列

小文字への変換

OR by space => (x | ' ')
Result is always lowercase even if letter is already lowercase
eg. ('a' | ' ') => 'a' ; ('A' | ' ') => 'a'

注釈:対象がすでに小文字であっても、結果は常に小文字です。

大文字への変換:

AND by underline => (x & '_')
Result is always uppercase even if letter is already uppercase
eg. ('a' & '_') => 'A' ; ('A' & '_') => 'A'

注釈:対象がすでに大文字であっても結果は常に大文字です。

反転文字の場合:

XOR by space => (x ^ ' ')
eg. ('a' ^ ' ') => 'A' ; ('A' ^ ' ') => 'a'

アルファベット内における文字の位置

AND by chr(31)/binary('11111')/(hex('1F') => (x & "\x1F")
Result is in 1..26 range, letter case is not important
eg. ('a' & "\x1F") => 1 ; ('B' & "\x1F") => 2

注釈:結果は1から26の範囲です。大文字か小文字かは重要ではありません。

アルファベット内における文字の位置の取得(大文字の場合のみ)

AND by ? => (x & '?') or XOR by @ => (x ^ '@')
eg. ('C' & '?') => 3 ; ('Z' ^ '@') => 26

アルファベット内における文字の位置の取得(小文字の場合のみ)

XOR by backtick/chr(96)/binary('1100000')/hex('60') => (x ^ '`')
eg. ('d' ^ '`') => 4 ; ('x' ^ '`') => 24

その他

シフトを使ったR5G5B5ピクセルフォーマットからR8G8B8ピクセルフォーマットへの高速な色変換

R8 = (R5 << 3) | (R5 >> 2)
G8 = (R5 << 3) | (R5 >> 2)
B8 = (R5 << 3) | (R5 >> 2)

注意:英語以外の文字を使用すると、正しい結果は得られません。

その他の出典