我在这里阅读了一个问题：C#中的数独算法
其中发布的解决方案之一是这段代码。
public static bool IsValid(int[] values) {
int flag = 0;
foreach (int value in values) {
if (value != 0) {
int bit = 1 << value;
if ((flag & bit) != 0) return false;
flag |= bit;
}
}
return true;
}
这个想法是检测值数组中的重复项；但我对自己不知道的东西感到很无助。有人能给我解释一下吗？
编辑：谢谢大家。有这么多好的回答，我不知道该选哪一个。现在我完全明白了。
这真是一个好主意。
基本上，它使用一个int标志（最初设置为零）作为“位数组”; 对于每个值，它检查标志中对应的位是否已设置，如果没有，则设置它。
如果相应的位位置已经设置，它知道相应的值已经被看到，因此数独的一部分无效。
更详细地说：
public static bool IsValid(int[] values)
{
// bit field (set to zero => no values processed yet)
int flag = 0;
foreach (int value in values)
{
// value == 0 => reserved for still not filled cells, not to be processed
if (value != 0)
{
// prepares the bit mask left-shifting 1 of value positions
int bit = 1 << value;
// checks if the bit is already set, and if so the Sudoku is invalid
if ((flag & bit) != 0)
return false;
// otherwise sets the bit ("value seen")
flag |= bit;
}
}
// if we didn't exit before, there are no problems with the given values
return true;
}
values = 1,2,3,2,5
迭代1：
bit = 1 << 1 bit = 10
if(00 & 10 != 00) false
flag |= bit flag = 10
迭代2：
bit = 1 << 2 bit = 100
if(010 & 100 != 000) false
flag |= bit flag = 110
迭代3：
bit = 1 << 3 bit = 1000
if(0110 & 1000 != 0000) false
flag |= bit flag = 1110
迭代4：
bit = 1 << 2 bit = 100
if(1110 & 0100 != 0000) TRUE 这个结果为true，意味着我们找到了一个重复的数字，并返回false。这个想法是设置数字的nth位，其中n是单元格的值。由于数独的值范围从1到9，因此所有位都在0-512的范围内。对于每个值，检查nth位是否已经设置，如果是，则找到了一个重复项。如果没有，则将nth位设置为1，累积已经使用过的数字在我们的检查数字（例如flag）上。这是一种比数组更快速地存储数据的方式。
foreach循环本身。 - mellamokb该程序检查数组中的值是否唯一。为此，它创建一个整数标志，并根据值数组中的值设置标志位。它检查特定位是否已经设置；如果是，则存在重复项并失败。否则，它设置该位。
以下是详细信息：
public static bool IsValid(int[] values) {
int flag = 0; // <-- Initialize your flags; all of them are set to 0000
foreach (int value in values) { // <-- Loop through the values
if (value != 0) { // <-- Ignore values of 0
int bit = 1 << value; // <-- Left-shift 1 by the current value
// Say for example, the current value is 4, this will shift the bit in the value of 1
// 4 places to the left. So if the 1 looks like 000001 internally, after shifting 4 to the
// left, it will look like 010000; this is how we choose a specific bit to set/inspect
if ((flag & bit) != 0) return false; // <-- Compare the bit at the
// position specified by bit with the corresponding position in flag. If both are 1 then
// & will return a value greater than 0; if either is not 1, then & will return 0. E.g.
// if flag = 01000 and bit = 01000, then the result will be 01000. If flag = 01000 and
//bit = 00010 then the result will be 0; this is how we check to see if the bit
// is already set. If it is, then we've already seen this value, so return false, i.e. not
// a valid solution
flag |= bit; // <-- We haven't seen this value before, so set the
// corresponding bit in the flag to say we've seen it now. e.g. if flag = 1000
// and bit = 0100, after this operation, flag = 1100
}
}
return true; // <-- If we get this far, all values were unique, so it's a valid
// answer.
}
int bit = 1 << value; //left bit shift - selects the bit that corresponds to value
if ((flag & bit) != 0) return false; //bitwise AND - checks the flag to see whether bit is already set
flag |= bit; // bitwise OR - sets the bit in the flag
values的总和是否等于唯一可能数字的总和（对于9x9游戏，它应该是45）在高级语言中会更有效率，不是吗？ - Anthony