2026-11-18
set_bit.cpp
#include <cstddef>
#include <cstdint>
#include <print>
#include <vector>
void set_bit(std::vector<std::uint64_t>& w,
std::size_t i,
bool b) {
}
w は、std::vector<bool> と同じように、真偽値を1ビットずつ詰めて持つ表です。0番目の値は w[0] の最下位ビットに入り、1番目の値はその1つ上のビットに入ります。こうして64個で語が埋まると、次の値は次の語の最下位ビットに入ります。ビットが1なら true、0なら false です。i 番目の値を b にする set_bit を書いてください。ほかのビットは変えません。w は i 番目の値を持てる長さがあるものとします。例では、呼ぶ前と呼んだ後の w の中身を {w[0], w[1]} の形で書きます。
入力例 1
w = {0, 0}; set_bit(w, 3, true);
出力例 1
{8, 0}
入力例 2
w = {8, 0}; set_bit(w, 64, true);
出力例 2
{8, 1}
入力例 3
w = {8, 1}; set_bit(w, 3, false);
出力例 3
{0, 1}
Reference
Reference
#include <cstddef>
#include <cstdint>
#include <print>
#include <vector>
void set_bit(std::vector<std::uint64_t>& w,
std::size_t i,
bool b) {
std::uint64_t mask = std::uint64_t{1}
<< (i % 64);
if (b)
w[i / 64] |= mask;
else
w[i / 64] &= ~mask;
}
1つの語には64個の値が入るので、i 番目の値は i / 64 番目の語の、下から i % 64 番目のビットにあります。参考実装は、そのビットだけが1の mask を作り、true にするときは |= でそのビットを1にし、false にするときは &= ~mask でそのビットだけを0にします。どちらも mask の0のビットに当たる位置は元の値のまま残るので、ほかの値は変わりません。掲載したのは参考実装で、唯一の正解ではありません。
mask は std::uint64_t{1} をずらして作ります。1 << (i % 64) と書くと 1 は int なので、32以上ずらしたときに int の幅を超え、未定義動作になります。入力例 1 では w[0] の下から3番目のビットが立って 8 になり、入力例 2 の i = 64 は w[1] の最下位ビットに当たるので w[1] が 1 になります。入力例 3 は w[0] の同じビットを0に戻すので、w[0] は 0 に戻ります。
std::vector<bool> も、要素をこのように語の中のビットとして持つよう特殊化されているので、要素1つが占めるのは1ビットです。