h**6
发帖数: 4160 | 1 已知整数 m ，其二进制形式有 k 位为1，打印出 0≤x≤m 所有满足以下条件的 x
x^(m-x) = m，其中^是异或运算符。
在 0≤m<2^n 范围内对每一个 m ，打印出所有的 x ，并求总复杂度。 | z******m
发帖数: 2 | 2 只有当两个数完全一样的时候，异或才会为0.
那么 X == M-X
所以 X=M/2
Only one solution? | z******m
发帖数: 2 | 3 怎么异或等于m了，我刚才看错题了？
两个数x,y，他们的和与异或的结果都是m，那么就是x,y两个数分m为1的位。
求出m有多少个1,如果是k个，那么x的个数就是2^k - 2。实际上就是枚举m的所有为1的
位的组合。 | b********h
发帖数: 119 | 4 试了一下，似乎是所有为1的位的全部子集。比如10的二进制表示为1010，那么一共有
两个x，即10（2）和1000（8）。14的话是1110，那么一共有六个，分别是2,4,6,8,10,
12
【在 h**6 的大作中提到】
: 已知整数 m ，其二进制形式有 k 位为1，打印出 0≤x≤m 所有满足以下条件的 x
: x^(m-x) = m，其中^是异或运算符。
: 在 0≤m<2^n 范围内对每一个 m ，打印出所有的 x ，并求总复杂度。
| h**6
发帖数: 4160 | 5 题目有错，已经再次编辑修改润色。
【在 z******m 的大作中提到】
: 怎么异或等于m了，我刚才看错题了？
: 两个数x,y，他们的和与异或的结果都是m，那么就是x,y两个数分m为1的位。
: 求出m有多少个1,如果是k个，那么x的个数就是2^k - 2。实际上就是枚举m的所有为1的
: 位的组合。
| x***y
发帖数: 633 | 6 The relation between m and x should be: every bit of m is bigger than or
equal to the corresponding bit of x. Otherwise, assume that lowest bit that
violates this relation is bit L, then there will be a carry for bit L+1 when doing m-x; Then in m, if bit L+1 is 1 originally, then it becomes 0 for the carry when doing m-x: if in x, bit L+1 is 1, then in m-x, bit L+1 is 1, the XOR result
is 0, not original 1; if in x, bit L+1 is 0, in m-x, it's 0, the XOR is 0,
not 1. It can be verified similarly when bit L+1 in m is 0 originally. So,
the relation must be true.
When the relation is true, x and m-x will be both 0 if m is 0 in the
corresponding bit or 1 and 0 or 0 and 1 if m is 1 in the corresponding bit.
So, the answer is that x is all the numbers whose bit is 0 if the bit in m
is 0 and whose bit can be 0 or 1 if the bit in m is 1.
【在 h**6 的大作中提到】
: 已知整数 m ，其二进制形式有 k 位为1，打印出 0≤x≤m 所有满足以下条件的 x
: x^(m-x) = m，其中^是异或运算符。
: 在 0≤m<2^n 范围内对每一个 m ，打印出所有的 x ，并求总复杂度。
| n*****y
发帖数: 361 | 7 学理论的吧？
你说的也对，但二楼比你解释的直观多了。
that
when doing m-x; Then in m, if bit L+1 is 1 originally, then it becomes 0 for
the carry when doing m-x: if in x, bit L+1 is 1, then in m-x, bit L+1 is 1
, the XOR result
,
【在 x***y 的大作中提到】
: The relation between m and x should be: every bit of m is bigger than or
: equal to the corresponding bit of x. Otherwise, assume that lowest bit that
: violates this relation is bit L, then there will be a carry for bit L+1 when doing m-x; Then in m, if bit L+1 is 1 originally, then it becomes 0 for the carry when doing m-x: if in x, bit L+1 is 1, then in m-x, bit L+1 is 1, the XOR result
: is 0, not original 1; if in x, bit L+1 is 0, in m-x, it's 0, the XOR is 0,
: not 1. It can be verified similarly when bit L+1 in m is 0 originally. So,
: the relation must be true.
: When the relation is true, x and m-x will be both 0 if m is 0 in the
: corresponding bit or 1 and 0 or 0 and 1 if m is 1 in the corresponding bit.
: So, the answer is that x is all the numbers whose bit is 0 if the bit in m
: is 0 and whose bit can be 0 or 1 if the bit in m is 1.
| h**6
发帖数: 4160 | 8 本题有三种方法可以解答：
1.直接筛选法：
for(int m=0; m<(1<
{
for(int x=0; x<=m; x++)
{
if((x^(m-x)) == m)
cout<
}
}
对于每一个固定的m，循环次数为 m+1 次，总循环次数为 2^(2n-1)+2^(n-1)，复杂度
为 O(2^(2n)) 或 O(4^n)。
2.按位枚举法：
int* one = new int[n];
for(int m=0; m<(1<
{
int mask = 1, k = 0;
for(int i=0; i
{
if(m & mask)
one[k++] = mask;
mask <<= 1;
}
for(int i=0; i<(1<
{
int mask2 = 1, x = 0;
for(int j=0; j
{
if(i & mask2)
x += one[j];
mask2 <<= 1;
}
cout<
}
}
delete []one;
对于每一个固定的m，循环次数为 k*2^k 次，总循环次数为 2*n*3^(n-1)，复杂度为 O
(n*3^n)，当 n 较大时(实测为n≥9)，复杂度比上一种方法小。
3.位运算法：
for(int m=0; m<(1<
{
for(int x=m; x>=0; x--)
{
x &= m;
cout<
}
}
对于每一个固定的m，循环次数为 2^k 次，总循环次数为 3^n，复杂度为 O(3^n)，比
以上两种方法小。 |
|
