2026-10-22
flip_bit.cpp
std::string flip_bit(std::string s, std::size_t bit) {
}
ファジングの入力 s の、bit 番目のビットだけを反転した文字列を返す flip_bit を書いてください。ビットの番号は、s[0] の最下位ビットを0番、s[0] の最上位ビットを7番とし、8番から先は s[1] の最下位ビットから同じ順に数えます。bit は s.size() * 8 より小さいものとし、空の s では呼びません。
入力例 1
flip_bit("a", 5)
出力例 1
"A"
入力例 2
flip_bit("ab", 8)
出力例 2
"ac"
入力例 3
flip_bit("1", 0)
出力例 3
"0"
Reference
std::string flip_bit(std::string s, std::size_t bit) {
s[bit / 8] ^= 1 << (bit % 8);
return s;
}
ビットの番号を8で割った商が何バイト目か、余りがそのバイトの何番目のビットかを表します。入力例 2 の8番は、商が1、余りが0なので s[1] の最下位ビットです。'b'(0x62)の最下位ビットを反転すると0x63の 'c' になります。反転には排他的論理和(exclusive OR、XOR)を使います。1 << (bit % 8) は目的の位置だけが1のマスクで、^= はマスクが1の位置を反転し、0の位置はそのまま残します。入力例 1 の 'a'(0x61)は5番のビットが反転して0x41の 'A' になります。
s は値で受け取っているので、関数の中で書き換えても呼び出し側の文字列は変わりません。元の入力を残したまま変異した入力を作れます。掲載したのは参考実装で、唯一の正解ではありません。AFL などのファザは、こうして1ビットずつ反転した入力を順に試す段階から変異を始めます1。
- AFL の決定的な変異の最初の段階は bitflip 1/1 と呼ばれ、入力の全ビットを1つずつ反転して実行します。続いて隣り合う2ビット、4ビット、1バイトと、反転する幅を広げていきます。