Namaran

Code daily. Without assist.

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。

  1. AFL の決定的な変異の最初の段階は bitflip 1/1 と呼ばれ、入力の全ビットを1つずつ反転して実行します。続いて隣り合う2ビット、4ビット、1バイトと、反転する幅を広げていきます。