2026-10-16
redelivery.cpp
#include <cstdint>
#include <iostream>
#include <vector>
struct Event {
std::uint8_t seq;
char path;
};
int main() {
std::vector<Event> events = {{254, 'a'}, {255, 'b'}, {255, 'b'}, {0, 'c'}, {1, 'd'}};
std::uint8_t last = 253;
for (const Event& e : events) {
if (e.seq <= last) {
continue;
}
last = e.seq;
std::cout << e.path;
}
std::cout << '\n';
}
ファイル変更の通知を順に処理し、再送された通知を読み飛ばすつもりのループです。通知元は通知ごとに8ビットの通し番号 seq を1ずつ増やして付け、255 の次は 0 に戻ります。入力は events の5件で、3件目は2件目の再送です。いまの出力は ab です。本来の出力は abcd です。
Answer
Wrong
if (e.seq <= last) {
b を処理した時点で last は 255 です。次の c の番号は 255 の次の 0 ですが、0 <= 255 は真なので再送とみなされて捨てられ、d の 1 も同じ理由で捨てられます。last は 255 のまま更新されないので、このあと届く通知はすべて 255 以下で、一つも処理されません。番号が一周した瞬間から、変更の監視が黙って止まります。
比べ方を差に変えて e.seq - last <= 0 としても直りません。std::uint8_t どうしの引き算は、両方が int に変換されてから行われるので、0 - 255 は -255 になり、やはり 0 以下です。
Right
if (static_cast<std::int8_t>(e.seq - last) <= 0) {
番号は 256 で割った余りとしてしか意味を持たないので、新旧は差を 256 で割った余りで判断します。2つの整数の差が 256 の倍数であることを、256 を法として合同(congruent modulo 256)といいます。int の -255 を std::int8_t に変換すると、-255 と合同な値のうち -128 以上 127 以下に収まる 1 になります1。差が 1 から 127 なら新しい通知、0 なら同じ通知、-128 から -1 なら古い通知として扱えるので、c と d は新しい通知として処理され、再送の b は差が 0 で捨てられます。この判定は、届く順序のずれが 127 件以内に収まることを前提にしています2。
- 符号付き整数への変換で値が範囲に収まらないときの結果は、C++17 までは処理系定義でした。C++20 から、変換先のビット数を N として、2 の N 乗を法として合同な値になると規格で決まっています。
- 一周する通し番号をこの形で比べる方法は、RFC 1982 で serial number arithmetic として定められており、TCP のシーケンス番号の比較も同じ考え方です。