Go to Qiita Advent Calendar Top
LoginSignup
1
1

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 1 year has passed since last update.

@arimoo(arimoo)

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

Posted at

本記事の趣旨

@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));
}
1
1
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
1
1

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?