ビット全探索を行うためのJulia言語におけるビット操作

これは何？

AtCoderでビット全探索の問題を解くために良く使うビット操作をまとめました。

ビットのn番目が立っているか

数字の５に対して右から２ビット目が立っているか？と３ビット目が立っているか？判定します。

julia> bit, n = 5, 2
(5, 2)

julia> bit & (1 << (n - 1)) ≠ 0
false

julia> n = 3
3

julia> bit & (1 << (n - 1)) ≠ 0
true

ビットのn番目が立っていないか

数字の５に対して右から２ビット目が立っているか？と３ビット目が立っているか？判定します。

julia> bit, n = 5, 2
(5, 2)

julia> bit & (1 << (n - 1)) == 0
true

julia> n = 3
3

julia> bit & (1 << (n - 1)) == 0
false

ビットに何個のフラグが立っているか

julia> count_ones(4)
1

julia> count_ones(5)
2

ビットのn番目を取得する

数字の５に対して右から２ビット目と3ビット目の値を取得しました。

julia> bit, n = 5, 2
(5, 2)

julia> (bit >> (n - 1)) & 1
0

julia> n = 3
3

julia> (bit >> (n - 1)) & 1
1

OR演算

julia> 1 | 2
3

julia> 2 | 3
3

XOR演算

⊻はveebarと入力する。

julia> 1⊻2
3

julia> 2⊻3
1