data-structures - 国际象棋棋盘所需的最少位数

Question

这是一个面试问题:

8x8 棋盘上两个位置的最小位数表示是多少？

我找到了答案http://www.careercup.com/question?id=4981467352399872

但是我无法理解作者想表达的意思:

You can represent 2^n values with n bits. However, you can represent 2^n + 2^(n-1) + 2^(n-2) + ... 1 = 2^(n+1) - 1 values with atmost n bits. So you can represent 2^11 - 1 = 2047 different values using just 10 bits.

我并不是在寻求对作者在答案中所建议内容的解释，但我更感兴趣的是解决问题本身。据我所知，由于有 64C2 = 2016 方法来表示 8x8 板上的两 block ，因此所需的最小位数应该是 11。但有人建议可以只用 10 位来表示棋盘。怎么办？

Answer 1

作者说你可以使用 5、6、7、8、9 和 10 位值来表示位置。

2016 年的二进制为 11111100000 (1024 + 512+ 256 + 128 + 64 + 32)

5 bits  (00000 -      11111) represent 32 positions
6 bits  (000000 -     111111) represent 64 positions
7 bits  (0000000 -    1111111) represent 128 positions
8 bits  (00000000 -   11111111) represent 256 positions
9 bits  (000000000 -  111111111) represent 512 positions
10 bits (0000000000 - 1111111111) represent 1024 positions

2016 年职位总数。

这可以用具有位集合的语言来实现，例如C++ bitset，有一个 size 函数来获取长度。

这是一个 2x2 板的示例，希望能更好地解释这一点。

对于 2x2 板，有 4C2 (6) 个位置

.x  x.  ..  xx  .x  x.
.x  x.  xx  ..  x.  .x

因此您可以使用 3 位 000、001、010、011、100、101 和 110

但是 6 是二进制 110 (4+2)，因此您可以使用 1 位 (0-1) 表示其中 2 个位置，使用 2 位 (00, 01, 10, 11) 表示其余 4 个位置。所以位置是:

0、1、00、01、10、11。