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

## 本記事の趣旨

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

<b>"((v - lo) & ~v & hi) != 0"</b>  

を、<b><font color="Red">順を追って、ちゃんと理解したい！！</font></b>  

...という記事です。  

https://qiita.com/i_saint/items/8842262da9a981c8e9e8

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

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

```cpp:元記事のソース
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となります。  

つまり<b><font color="Red">(v - lo) & ~v & hiが0ではない場合、vに\0を含んでいると言えます。</font></b>  

...もし↑で理解できたなら、以下は**読まなくても大丈夫**です！  
私は多分、理解できてない状態で読んでも<b><font color="Red">判らなかったと思います！！</font></b>  

## チェック対象v

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

```C#:incVとexcV

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

```

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

| 変数 | 上位byte | <--- | ---> | 下位byte |
| - | - | - | - | - |
| incV | 1111 0001 | 1000 0111 | <font color="Red">0000 0000</font> | 1111 1111 |
| excV | 1111 0001 | 1101 0010 | 0011 1010 | 1011 0000 |

...になります。  
<b><font color="Red">赤字の部分が\0です。</font></b>  

## ~v

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

```C#:~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

```C#: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

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

```C#:v - lo

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

```

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

|  | 上位byte | <--- | ---> | 下位byte |
| - | - | - | - | - |
| **incVの計算** |
| incVから | 1111 0001 | 1000 0111 | <font color="Red">0</font>000 0000 | 1111 1111 |
| *loを引く* | *0000 0001* | *0000 0001* | *0000 0001* | *0000 0001* |
| 結果(minusLoIncV) | 1111 0000 | 1000 0101 | <font color="Red">1</font>111 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 |

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

## (v - lo) & ~v

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

```C#:(v - lo) & ~v

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

```

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

|  | 上位byte | <--- | ---> | 下位byte |
| - | - | - | - | - |
| **incVの計算** |
| minusLoIncV | 1111 0000 | 1000 0101 | <font color="Red">1</font>111 1111 | 1111 1110 |
| *＆turnIncV* | *0000 1110* | *0111 1000* | *<font color="Red">1</font>111 1111* | *0000 0000* |
| 結果(and1IncV) | **0**000 0000 | **0**000 0000 | <b><font color="Red">1</font></b>111 1111 | **0**000 0000 |
| **excVの計算** |
| minusLoExcV | 1111 0000 | 1101 0001 | 0011 1001 | 1010 1111 |
| *＆turnExcV* | *0000 1110* | *0010 1101* | *1100 0101* | *0100 1111* |
| 結果(and1ExcV) |  **0**000 0000 | **0**000 0001 | **0**000 0001 | **0**000 1111 |

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

## (v - lo) & ~v & hi

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

```C#:(v - lo) & ~v & hi

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

```

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

|  | 上位byte | <--- | ---> | 下位byte |
| - | - | - | - | - |
| **incVの計算** |
| and1IncV | 0000 0000 | 0000 0000 | <b><font color="Red">1</font></b>111 1111 | 0000 0000 |
| *＆hi* | *1000 0000* | *1000 0000* | *1000 0000* | *1000 0000* |
| 結果(and2IncV) | 0000 0000 | 0000 0000 | <b><font color="Red">1000 0000</font></b> | 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 |

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

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

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

...となります。  
<b><font color="Red">ここまでお疲れ様でした！</font></b>  

## 改めて結論(再掲)

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となります。  

つまり<b><font color="Red">(v - lo) & ~v & hiが0ではない場合、vに\0を含んでいると言えます。</font></b>  

## 蛇足気味の補足

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

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

## コード(C#)

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

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

```C#

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));
}
```

</div></details>