本記事の趣旨

@i_saint(Seiya Ishibashi)さんの記事「strlen() の深淵」に出てくる\0の判定式

"((v - lo) & ~v & hi) != 0"

を、順を追って、ちゃんと理解したい！！

...という記事です。

元記事のソースはC++ですが、個人的にC#使いなのでC#で記述します。
...が、どの言語でも原理は一緒かと思います。
またulong(符号なし64bit)だと横に長いので、uint(符号なし32bit)で記述します。

そして本記事では2進数/16進数の説明は行いません。
(ぐぐれば素敵な記事が沢山あるかと思います！)

元記事のソース

bool contains_zero_byte(uint64_t v)
{
    constexpr uint64_t hi = 0x8080808080808080;
    constexpr uint64_t lo = 0x0101010101010101;
    return ((v - lo) & ~v & hi) != 0;
}

先に結論を書いてみる

vの各バイトから1(lo)を引く事でvのとあるバイト(以下Vn)が0(＝\0)の場合に限り、
引き算による桁の繰り下がりで先頭ビット(hi)に1が立ちます。
(Vn > 0の場合、1引いても最小0なので絶対に桁の繰り下がりが起こらない)

Vn > 0 の場合、

先頭ビットが1 → ~vで0にされたANDが立ち塞がる
先頭ビットが0 → 絶対に桁の繰り下がりが起こらないので先頭ビットは0のまま

...なのでvに\nを含まない場合、
(v - lo) & ~v の結果、各バイトの先頭ビットが1になる事はありません。
(hiとAND取っても結果は0)

Vnが0の場合は~Vの先頭ビットも1になるので、
Vn - 1で繰り下がりが発生した場合だけ (v - lo) & ~v の結果、先頭ビットが1となります。

つまり(v - lo) & ~v & hiが0ではない場合、vに\0を含んでいると言えます。

...もし↑で理解できたなら、以下は読まなくても大丈夫です！
私は多分、理解できてない状態で読んでも判らなかったと思います！！

チェック対象v

\0を含む(incV)・含まない(excV)の2個用意します。

incVとexcV


uint incV = 0xF18700FF; //\0を含む
uint excV = 0xF1D23AB0; //\0を含まない

これを2進数で表現すると、

変数	上位byte	<---	--->	下位byte
incV	1111 0001	1000 0111	0000 0000	1111 1111
excV	1111 0001	1101 0010	0011 1010	1011 0000

...になります。
赤字の部分が\0です。

~v

順序が変わりますが、先に~vを用意します。
"~"はビットを反転させる演算子です。

~v


uint turnIncV = ~incV;
uint turnExcV = ~excV;

これを2進数で表現すると、

変数	上位byte	<---	--->	下位byte
turnIncV	0000 1110	0111 1000	1111 1111	0000 0000
turnExcV	0000 1110	0010 1101	1100 0101	0100 1111

...になります。
最初のvが、綺麗に反転しているのが判りますね。

hiとlo

hiとlo


uint hi = 0x80808080;
uint lo = 0x01010101;

これを2進数で表現すると、

変数	上位byte	<---	--->	下位byte
hi	1000 0000	1000 0000	1000 0000	1000 0000
lo	0000 0001	0000 0001	0000 0001	0000 0001

...になります。
各バイトの上位ビット・下位ビットを綺麗に表現していますね。

v - lo

いよいよ本題に入りました！

v - lo


uint minusLoIncV = incV - lo;
uint minusLoExcV = excV - lo;

これを2進数で表現すると、

	上位byte	<---	--->	下位byte
incVの計算
incVから	1111 0001	1000 0111	0000 0000	1111 1111
loを引く	0000 0001	0000 0001	0000 0001	0000 0001
結果(minusLoIncV)	1111 0000	1000 0101	1111 1111	1111 1110
excVの計算
excVから	1111 0001	1101 0010	0011 1010	1011 0000
loを引く	0000 0001	0000 0001	0000 0001	0000 0001
結果(minusLoExcV)	1111 0000	1101 0001	0011 1001	1010 1111

...になります。
注目すべきは赤字の部分、ここだけ上位ビットが変化しています。
(引き算による桁の繰り下がりが発生)

(v - lo) & ~v

先の引き算の結果と~vのANDを計算します(AND計算1回目)

(v - lo) & ~v


uint and1IncV = minusLoIncV & turnIncV;
uint and1ExcV = minusLoExcV & turnExcV;

これを2進数で表現すると、

	上位byte	<---	--->	下位byte
incVの計算
minusLoIncV	1111 0000	1000 0101	1111 1111	1111 1110
＆turnIncV	0000 1110	0111 1000	1111 1111	0000 0000
結果(and1IncV)	0000 0000	0000 0000	1111 1111	0000 0000
excVの計算
minusLoExcV	1111 0000	1101 0001	0011 1001	1010 1111
＆turnExcV	0000 1110	0010 1101	1100 0101	0100 1111
結果(and1ExcV)	0000 0000	0000 0001	0000 0001	0000 1111

...になります。
注目すべきは赤字の部分、唯一ここだけ上位ビットが1が残りました。
他の結果の上位ビットが全て0な事も確認しましょう！

(v - lo) & ~v & hi

いよいよ左辺側の計算の最後、
先のANDの結果とhiのANDを計算します(AND計算2回目)

(v - lo) & ~v & hi


uint and2IncV = and1IncV & hi;
uint and2ExcV = and1ExcV & hi;

これを2進数で表現すると、

	上位byte	<---	--->	下位byte
incVの計算
and1IncV	0000 0000	0000 0000	1111 1111	0000 0000
＆hi	1000 0000	1000 0000	1000 0000	1000 0000
結果(and2IncV)	0000 0000	0000 0000	1000 0000	0000 0000
excVの計算
and1ExcV	0000 0000	0000 0001	0000 0001	0000 1111
＆hi	1000 0000	1000 0000	1000 0000	1000 0000
結果(and2ExcV)	0000 0000	0000 0000	0000 0000	0000 0000

...となり、赤字部分の唯一\0だったincVの下から2バイト目(表の--->)だけが非0の結果が得られました！

最後は右辺値0との不一致比較(!= 0)ですが、
上記の結果から

and2IncV != 0 ： TRUE → \0を含む
and2ExcV != 0 ： FALSE → \0を含まない

...となります。
ここまでお疲れ様でした！

改めて結論(再掲)

vの各バイトから1(lo)を引く事でvのとあるバイト(以下Vn)が0(＝\0)の場合に限り、
引き算による桁の繰り下がりで先頭ビット(hi)に1が立ちます。
(Vn > 0の場合、1引いても最小0なので絶対に桁の繰り下がりが起こらない)

Vn > 0 の場合、

先頭ビットが1 → ~vで0にされたANDが立ち塞がる
先頭ビットが0 → 絶対に桁の繰り下がりが起こらないので先頭ビットは0のまま

...なのでvに\nを含まない場合、
(v - lo) & ~v の結果、各バイトの先頭ビットが1になる事はありません。
(hiとAND取っても結果は0)

Vnが0の場合は~Vの先頭ビットも1になるので、
Vn - 1で繰り下がりが発生した場合だけ (v - lo) & ~v の結果、先頭ビットが1となります。

つまり(v - lo) & ~v & hiが0ではない場合、vに\0を含んでいると言えます。

蛇足気味の補足

uint x = 0 - 1の結果がFFFFFFFFと(※)、
引き算してるのに結果が増えるのに違和感ある人もいるかもですが
(特に初期値incVを0にした時とか...)、
これはuint(やulong)の世界線がFFFFFFFFの次が00000000という円環の理に囚われている為に仕方がないのです！

※C#では、このコードはエラーになります。即値の0ではなくuint v=0でv-1とすれば良いです。

コード(C#)

雑なコードなので折り畳んで置いておきます。

検証したい方はどうぞ(NET6/WinFormsだけど中身はどこでも動くと思います)


string to2(uint v)
{
    string w = Convert.ToString(v, 2);
    w = w.PadLeft(32, '0');

    StringBuilder sb = new StringBuilder();

    for (int i = 0; i < 4; i++)
    {
        sb.Append(w.Substring(i * 8, 8));

        if (i < 3)
        {
            sb.Append(" ");
        }
    }

    sb.Append($" |n={v}");

    return sb.ToString();
}

private void button2_Click(object sender, EventArgs e)
{
    uint incV = 0xF18700FF; //\0を含む
    uint excV = 0xF1D23AB0; //\0を含まない

    Debug.WriteLine("<incV>");
    Debug.WriteLine(to2(incV));
    Debug.WriteLine("<excV>");
    Debug.WriteLine(to2(excV));

    uint turnIncV = ~incV;
    uint turnExcV = ~excV;

    Debug.WriteLine("<turnIncV>");
    Debug.WriteLine(to2(turnIncV));
    Debug.WriteLine("<turnExcV>");
    Debug.WriteLine(to2(turnExcV));

    uint hi = 0x80808080;
    uint lo = 0x01010101;

    Debug.WriteLine("<hi>");
    Debug.WriteLine(to2(hi));
    Debug.WriteLine("<lo>");
    Debug.WriteLine(to2(lo));

    uint minusLoIncV = incV - lo;
    uint minusLoExcV = excV - lo;

    Debug.WriteLine("<minusLoIncV>");
    Debug.WriteLine(to2(minusLoIncV));
    Debug.WriteLine("<minusLoExcV>");
    Debug.WriteLine(to2(minusLoExcV));

    uint and1IncV = minusLoIncV & turnIncV;
    uint and1ExcV = minusLoExcV & turnExcV;

    Debug.WriteLine("<and1IncV>");
    Debug.WriteLine(to2(and1IncV));
    Debug.WriteLine("<and1ExcV>");
    Debug.WriteLine(to2(and1ExcV));

    uint and2IncV = and1IncV & hi;
    uint and2ExcV = and1ExcV & hi;

    Debug.WriteLine("<and2IncV>");
    Debug.WriteLine(to2(and2IncV));
    Debug.WriteLine("<and2ExcV>");
    Debug.WriteLine(to2(and2ExcV));
}