关于本题中的位运算
public boolean f(int maxChoosableInteger, int desiredTotal, int choos) {
if (desiredTotal <= 0) {
return false;
}
if (dp.containsKey(choos)) {
return dp.get(choos);
}
for (int i = 1;i <= maxChoosableInteger;i++) {
if ((choos & (1 << i)) == 0) {
if (!f(maxChoosableInteger,desiredTotal-i,choos | (1 << i))) {
dp.put(choos,true);
return true;
}
}
}
dp.put(choos,false);
return false;
}
怎么理解这个？
choos & (1 << i)) == 0 // 判断i是否被拿
choos | (1 << i) // 将第i位bit位标为1
// 举个例子
//假如整数池是这样
1 2 3 4 5 6 7 8 9 10
// 最开始打算用一个一维数组表示 可以这样
value : 0 0 0 0 0 0 0 0 0 0 0 -> int[]
index : 0 1 2 3 4 5 6 7 8 9 10
// 由于线性结构对于改动态规划来说复杂度较高,所有将参数int[]降维成int类型
// 利用int32个bit位表达信息 那么可以这样
0 0 0 0 0 0 0 0 0 0 0 -> int
// 此时我们将0视为未拿 1视为已拿
// 如果 9被拿了那么从右往左以0位置起始就是第9位bit位标为1
0 1 0 0 0 0 0 0 0 0 0 -> int
// 假如10已经被拿了但是此时想拿9怎么标 将 1左移9位并且与choos做或运算 也就是这种表达：choos | (1 << 9)
// 由于 : 0 | 0 = 0; 0 | 1 = 1; 1 | 1 = 1；
choos: 1 0 0 0 0 0 0 0 0 0 0 -> int
help: 0 1 0 0 0 0 0 0 0 0 0 -> int
ans: 1 1 0 0 0 0 0 0 0 0 0 -> int
// 假如10,9,7,1都被拿了如何判断9是否被拿 可以利用1左移9位并且与choos做与运算也就是这种表达：choos & (1 << 9)
// 如果 ans != 0; 说明9已经被拿了
// 由于 : 0 & 0 = 0; 0 & 1 = 0; 1 & 1 = 1;
choos: 1 1 0 1 0 0 0 0 0 1 0 -> int
help: 0 1 0 0 0 0 0 0 0 0 0 -> int
ans: 0 1 0 0 0 0 0 0 0 0 0 -> int
标签：
