POSTD PRODUCED BY NIJIBOX

POSTD PRODUCED BY NIJIBOX

ニジボックスが運営する
エンジニアに向けた
キュレーションメディア

POSTD PRODUCED BY NIJIBOX

POSTD PRODUCED BY NIJIBOX

ニジボックスが運営する
エンジニアに向けた
キュレーションメディア

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

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

文字列

小文字への変換

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)

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

その他の出典

監修者
監修者_古川陽介
古川陽介
株式会社リクルート プロダクト統括本部 プロダクト開発統括室 グループマネジャー 株式会社ニジボックス デベロップメント室 室長 Node.js 日本ユーザーグループ代表
複合機メーカー、ゲーム会社を経て、2016年に株式会社リクルートテクノロジーズ(現リクルート)入社。 現在はAPソリューショングループのマネジャーとしてアプリ基盤の改善や運用、各種開発支援ツールの開発、またテックリードとしてエンジニアチームの支援や育成までを担う。 2019年より株式会社ニジボックスを兼務し、室長としてエンジニア育成基盤の設計、技術指南も遂行。 Node.js 日本ユーザーグループの代表を務め、Node学園祭などを主宰。