abs() の正体
Hacker's Delight という書籍があり、さまざまなフレームワークで参照文献として利用されていました。
OpenJDK の実装など見ているとコメントでよく見かけます。
(以下は OpenJDK の reverse_bits の実装で、コメントに Hacker's Delight という文字を見つけることができます。)
public:
inline T operator()(T v) const {
// Based on Hacker's Delight Section 7-1
U x = static_cast<U>(v);
x = ((x & rep_5555) << 1) | ((x >> 1) & rep_5555);
x = ((x & rep_3333) << 2) | ((x >> 2) & rep_3333);
x = ((x & rep_0F0F) << 4) | ((x >> 4) & rep_0F0F);
return byteswap(static_cast<T>(x));
}
};
出版が2012年なので、2025年の現状はどうなっているか気になったので、 abs を例に情報のアップデートを行いました。
目的は、abs() 関数を今のモダンアーキテクチャではどのように実装しているか調べたというものです。
対象関数
今回、簡単な abs の実装を対象にしたいと思います。
ご存知だと思いますが、cppreference.com を見てもらえれば以下のようになっています。
Computes the absolute value of the integer number num. The behavior is undefined if the result cannot be represented by the return type.
If std::abs is called with an unsigned integral argument that cannot be converted to int by integral promotion, the program is ill-formed.
以下のように絶対値を返してくれます。
std::cout << std::showpos << "abs(-123) = " << std::abs(-123) << '\n';
- showpos は正の符号も表示します。
出力：
abs(-123) = +123
Hacker's Delight での定義例
Hacker's Delight では、マシンが絶対値の命令を持たない 場合は以下のようにビット操作が使われるように説明されています。
1つ目は y にxを32ビットずらしているので2の補数の最上位ビットを取れる。つまり
- x≥0（正またはゼロ）の場合: y=0
- x<0（負）の場合: y=−1（すべてのビットが 1）
となる。
この y を利用して元の値との排他的論理和 (X-OR) を取れば絶対値が取れるというものです。
- x≥0 (正)
- y=0
- (x⊕0)−0=x−0
- x (abs(x))
- x<0 (負)
- y=−1
- (x⊕(−1))−(−1)
- (−x) (abs(x))
つまり2の補数の最上位ビットを使い絶対値を取るというものです。
if 文で実装した場合
if 文でも実装できます。
if (x < 0) {
return -1 * x;
} else {
return x;
}
マシン語で考えると、 cmp / jl / neg / mov / ret が最低限必要になり、5ステップ必要になります。
(上記 else のブロックになった場合)
しかし、先ほどのビット演算の場合は、 ASRS / EOR / ADDS の3ステップで必ず終わります。つまり if文より abs() 関数を使った方が 2 ステップの高速化を図ることができます。
実験サンプルコード
今回の検証では以下のサンプルコードを利用します。
#include <stdio.h>
#include <stdlib.h>
int main(int argc, char* argv[]) {
int input_val = -222;
if (argc > 1) {
input_val = atoi(argv[1]);
}
int a = abs(input_val);
printf("abs result: %d\n", a);
return 0;
}
最後に printf で abs() 関数の実行結果 a を出力するようにしてください。コンパイラの最適化によっては計算結果が削除される場合があるので、最後までメモリ上に保存させるようにしましょう。
アーキテクチャごとの検証
今回、Apple M4 と x86_64、おまけとして WASM で検証をしてみます。
Apple M4
利用した mac mini(M4) だと ARM64 で clang を利用しました。
最適化ビルドとバイナリーコードの解析
$ clang -O3 abs.c -o a.out
$ objdump -D a.out
結果 (TEXTのみ):
0000000100000460 <_main>:
100000460: d10083ff sub sp, sp, #0x20
100000464: a9017bfd stp x29, x30, [sp, #0x10]
100000468: 910043fd add x29, sp, #0x10
10000046c: 7100081f cmp w0, #0x2
100000470: 5400008b b.lt 0x100000480 <_main+0x20>
100000474: f9400420 ldr x0, [x1, #0x8]
100000478: 9400000d bl 0x1000004ac <_printf+0x1000004ac>
10000047c: 14000002 b 0x100000484 <_main+0x24>
100000480: 12801ba0 mov w0, #-0xde ; =-222
100000484: 7100001f cmp w0, #0x0
100000488: 5a805408 cneg w8, w0, mi
10000048c: f90003e8 str x8, [sp]
100000490: 90000000 adrp x0, 0x100000000 <_printf+0x100000000>
100000494: 91131000 add x0, x0, #0x4c4
100000498: 94000008 bl 0x1000004b8 <_printf+0x1000004b8>
10000049c: 52800000 mov w0, #0x0 ; =0
1000004a0: a9417bfd ldp x29, x30, [sp, #0x10]
1000004a4: 910083ff add sp, sp, #0x20
1000004a8: d65f03c0 ret
100000488 で cneg w8, w0, mi となっている箇所が abs 関数のようです。
ARM の仕様書を見ると CNEG は条件が一致した場合はレジスターの値を負数を登録し、条件に一致しない場合はレジスターの値をそのまま登録するとなっている。
つまり、w0 レジストリーの値が負数(mi: minus)の場合、負数を w8 に格納し、整数であれば w0 の値をそのまま w8 に格納することにより絶対値を取得している
Hacker's Delight では「マシンが絶対値の命令を持たない場合」とあったので、mac の M4 チップセットでは CNEG という命令があるのでそれを利用したということになります。
調べてはいませんが、ARM のほとんどの CPU にはこの命令があるのではないでしょうか。
x86(Intel)
利用した Dell XPS(Intel) だと x86_64 で clang を利用しました。
最適化ビルドとバイナリーコードの解析
$ clang -O3 abs.c -o a.out
$ objdump -D a.out
結果 (TEXTのみ):
0000000000001150 <main>:
1150: 50 push %rax
1151: b8 22 ff ff ff mov $0xffffff22,%eax
1156: 83 ff 02 cmp $0x2,%edi
1159: 7c 10 jl 116b <main+0x1b>
115b: 48 8b 7e 08 mov 0x8(%rsi),%rdi
115f: 31 f6 xor %esi,%esi
1161: ba 0a 00 00 00 mov $0xa,%edx
1166: e8 d5 fe ff ff call 1040 <strtol@plt>
116b: 89 c6 mov %eax,%esi
116d: f7 de neg %esi
116f: 0f 48 f0 cmovs %eax,%esi
1172: 48 8d 3d 8b 0e 00 00 lea 0xe8b(%rip),%rdi # 2004 <_IO_stdin_used+0x4>
1179: 31 c0 xor %eax,%eax
117b: e8 b0 fe ff ff call 1030 <printf@plt>
1180: 31 c0 xor %eax,%eax
1182: 59 pop %rcx
1183: c3 ret
116f で cmovs %eax,%esi となっている箇所が abs 関数のようです。
AMD の仕様書を見ると cmovs は条件が一致した場合はレジスターの値を負数を登録するとなっている。
https://developer.arm.com/documentation/ddi0602/2025-06/Base-Instructions/CNEG--Conditional-negate--an-alias-of-CSNEG-
つまり、 mov %eax,%esi で入力値を %eax に格納し、入力値の負数を %esi に入れておく。
cmovs で %esi が負数だった場合はその負数を %eaxに入れる。
これにより絶対値が %eax に格納されるようになっている。
では Delight の実装はどこで使われてる？
主流のCPUでは絶対数を扱うための命令セットがあるので、Hacker's Delight で紹介されているビット操作を行うものは利用されていなかった。
ではビット操作で絶対値を使うケースはどこにあるのか？
WASM でビルドする
CPU 依存をさせないため、先ほどと同じサンプルコードを WASM でビルドしてみます。
em++ abs.c
wasm-objdump -d a.out.wasm
バイナリ：
0002ad: 20 02 | local.get 2 #入力値 x を取得
0002af: 28 02 10 | i32.load 2 16 #定数 31 (32ビット整数の最上位ビットのインデックス)
0002b2: 21 03 | local.set 3
0002b4: 20 03 | local.get 3
0002b6: 41 1f | i32.const 31
0002b8: 75 | i32.shr_s # 算術右シフト
0002b9: 21 04 | local.set 4 # マスク値を local 4 に格納
0002bb: 20 02 | local.get 2
0002bd: 20 03 | local.get 3 # 入力値 x を再度取得
0002bf: 20 04 | local.get 4 # マスク値 s を取得
0002c1: 73 | i32.xor # x XOR s を計算
0002c2: 20 04 | local.get 4 # マスク値 s を再度取得
0002c4: 6b | i32.sub # (x XOR s) - s を計算
抜粋ですが、このコードを見ると入力値に対してシフト演算子を行い、Hacker's Delight の絶対値と同じ計算をしていることがわかりました。
まとめ
Hacker's Delight に記載のある絶対値計算は今でも利用されているみたいです。
ただ、ARM64 / x86_64 の例を見ての通り、専用の符号判定命令セットが用意されていてビルド時にはそれが利用されるようです。
Discussion