c - In LRU square algorithm, is the least-recently-used row always zero?

Question

My copy of Hacker's Delight is at home, and the web resources I've found aren't clear on this detail.

I have written the following 8-level LRU, using the well-known "row-column square" algorithm. (Is there a better name?).

#include <stdint.h>

typedef union {
  uint8_t rows[8];  
  uint64_t cols;
} lru_state;

void lru_init(lru_state *this) {
  this->cols=0;
}

void lru_up(lru_state *this, int used /* in 0..7 */) {
  this->rows[used]=0xff;
  this->cols &= ~(0x0101010101010101 << used);
}

int lru_get(lru_state *this) {
  int i;
  for (i=1; i<8 ; i++) {
    if (0==(this->rows[i])) return i;
  }
  return 0;
}

I would like confirmation of my assumption that the least-recently-used row will be all zeroes. It seems to work, but I don't have the math to prove it to my satisfaction.

So, is this right? Or do I need to compute the minimum Hamming weight for each row?

Answer 1

你的假设是正确的。

我们可以用反证法证明：

假设 LRU 候选（具有最多零位的字节）是 c，并且在位置 x 中设置了一个位。

这意味着在行 c 之后没有使用行 x，因此 x 必须具有 c 具有的所有零位，加上位置 x 的零。这是一个矛盾，因为 c 是具有最多零位的字节，因此我们得出结论 c 不能设置任何位。