能力值:
(RANK:420 )
2 楼
1) 奇數很明顯;至於偶數,就是那個數學式中可以整除4, 但不能整除8的那個判斷式。
,(2) ⊕ (6) = (-2) ⊕ (-6) ===>這剛好是個很棒的例外 exception.
能力值:
( LV4,RANK:50 )
3 楼
1. A,B 两数相等应该也算是一种特例,因为 0 没有正负之分
2. 考虑偶数的情况下,发现虽然A,B取8以内只有 2 xor 6 = (-2) xor (-6) 这个特例,但是8以外这样的情况还很多,比如:
6 xor 10, 6 xor 14, ..., 86 xor 90, ...
6 xor 10, (00000006 xor 0000000A) = (FFFFFFFA xor FFFFFFF6) 86 xor 90, (00000056 xor 0000005A) = (FFFFFFAA xor FFFFFFA6)
利用之前那个TestXor()函数,写了个程序枚举A, B同为偶数时的例外情况。附件中是100以内的输出结果和源码(源代码没有整理过,随便看看吧)
上传的附件:
能力值:
(RANK:420 )
4 楼
觀察 0 到 7 的 two's complement,然後看看結果如下:
0)
000
Not
-----------
111
+ 1
-----------
1000
1)
001
Not
-----------
110
+ 1
-----------
111 2)
010
Not
-----------
101
+ 1
-----------
110
3)
011
Not
----------
100
+ 1
-----------
101
4)
100
Not
-----------
011
+ 1
-----------
100
5)
101
Not
-----------
010
+ 1
-----------
011
6)
110
Not
-----------
001
+ 1
-----------
101
7)
111
Not
-----------
000
+ 1
-----------
001
0) 的結果之 bits 型態為 1000,最後的 3 個 bits 為 0.
4) 的結果之 bits 型態為 100,最後的 3 個 bits 為 0.
以 4) 為例子,轉換前的 bits 型態是 100,轉換後的 bits 型態還是 100,因此轉換前、後的bits 型態都一樣。
以 0)為例子,轉換前的 bits 型態是 000,轉換後的 bits 型態是 1000,取最右邊 3 個 bits 為 000,所以轉換前、後的 bits 型態也都一樣。
可是,若 integer 為 zero ,那意義不大;因此,只能把 3 個 bits length 變成 4 bits length,那就變成 1000 的型態。而最右邊的 bits length 若為 1000 型態者,必與 8 有關。
===== 接著討論 deryope 的例外 sample =====
討論以下 pairs 的關係,例如討論 2 跟 6 關係,我用 (2,6); (6,10); (6,14); (10,14); (86,90) 總共 五個 pairs。
g c d 為 greatest common divisor 之縮寫。
g c d(2,6)=2
g c d(6,10)=2
g c d(6,14)=2
g c d(10,14)=2
g c d(86,90)=2
我所提的證明,保證條件成立,也有規則可循。
deryope 所提的例子,條件也成立,但有沒固定規則可循?我不知道,唯一我能找出這個規則的是 g c d(a,b)=2.
補充1:
將 (2,6) 同乘 3 倍,為 (6,18)
g c d(2,6)=2.
g c d(6,18)=6.
2⊕6=-2⊕-6.
6⊕18=-6⊕-18.
可見g c d(a,b)=2 不是唯一可做為判斷的條件。
能力值:
( LV9,RANK:170 )
5 楼
楼主是台湾或香港人?
能力值:
( LV2,RANK:10 )
6 楼
下次用简体中文吧
能力值:
( LV4,RANK:50 )
7 楼
先说明这个思路不是我想出来的,昨天吃饭时和几个哥们聊起这个问题,他们倒是从二进制角度解释了这一现象。其实版主的思路已经很接近了,就是看二进制的最后几位来确定xor后结果是否相等。
我们知道『
负数 = 正数取反+1 』,因为偶数取反+1后会有进位,导致了可能 (A ⊕ B) != (-A ⊕ -B)
总结来说,就是看二进制进位后停在哪一位上。
一旦两个数+1操作进位的位数相同,就产生 (A ⊕ B) = (-A ⊕ -B) 举个例子:
我们先看偶数的情况: 2 => 0x2 => (0010 )b 6 => 0x6 => (0110 )b 14 => 0xE => (1110 )b 原始值 取反结果 2 => (... 0000 0010 )b => (1111 ... 1111 1101 )b 6 => (... 0000 0110 )b => (1111 ... 1111 1001 )b +1操作导致进位 取反结果 +1后 2 => (1111 ... 1111 1101 )b +1 => (1111 ... 1111 1110 )b 6 => (1111 ... 1111 1001 )b +1 => (1111 ... 1111 1010 )b | | 注意这个0 进位操作到这个地方为止,进位1次 两个数进位的位数相同,所以XOR后的结果相等。同理可以推出 14 (1110)b 与 2、6 之间异或也是满足 A ⊕ B = -A ⊕ -B 的。 类推这样的数有: 2 (0000 0010 )b 6 (0000 0110 )b 10 (0000 1010 )b 14 (0000 1110 )b 18 (0001 0010 )b 22 (0001 0110 )b 26 (0001 1010 )b .. ... 这还只是进位1次的情况,按照上面说的只要进位位数相同就能满足条件,于是还能推出: 4 (0000 0100 )b 12 (0000 1100 )b 20 (0001 0100 )b 28 (0001 1100 )b .. ... 这是进位两次的数(也就是4的倍数),还能推出进位3次、4次... 总之无穷无尽。 按照这个理论,两个数都是奇数的情况也很容易解释了,奇数取反后末尾为 (...0)b,+1后不会进位(也就是进位0次的情况),所以100%相等。一奇一偶也一样,奇数取反+1不进位,但偶数却进位了(也就是进位的位数不相同),所以异或后结果不相等。
能力值:
( LV4,RANK:50 )
8 楼
不是,不过繁体字也能看懂吧,文言文不都是繁体字?
总之随意了,尊重个人习惯,用繁体用简体都不影响交流
忘了,附带一个显示两个数计算结果和16进制的程序,方便验证结果。
u_int32_t a, b;
u_int32_t temp;
do {
a = 0; b = 0;
printf("\n请输入两个正整数A,B (以逗号分割): "); scanf("%d,%d", &a, &b);
// 输出下计算结果
temp = (-a)^(-b);
printf("%d xor %d, C1=0x%.8X, C2=0x%.8X\n", a, b, (a^b), temp);
printf(" (%.8X xor %.8X) = (%.8X xor %.8X)\n", a, b, -a, -b);
}while ( a || b );
之前那个枚举这些数的程序,删掉了那些没用的代码,具体看附件中的程序
上传的附件:
能力值:
(RANK:420 )
9 楼
請問有沒發現 一個跟 4 影關係,另一個跟8有關係,都差,都差8.
能力值:
( LV9,RANK:180 )
10 楼
看到后面那个, 我就想到Innova问的 是4的倍数, 但不要8的倍数
那不就是 4*奇数
能力值:
( LV4,RANK:50 )
11 楼
嗯,这两个例子刚好一个是+4,另一个是+8,类推3次进位的就是+16了(8,24,40,...)。
至于间隔多少,是由二进制的尾数决定的:
前三个:
2 .... ..[COLOR="Red"]1[/COLOR]0 (+ 4) 2,6,10,14...
4 .... .[COLOR="red"]1[/COLOR]00 (+ 8) 4,12,20...
8 .... [COLOR="red"]1[/COLOR]000 (+16) 8,24,40...
再往后继续乘2(1继续向前挪动):
16 ...[COLOR="red"]1[/COLOR] 0000 (+32) ...
32 ..[COLOR="red"]1[/COLOR]0 0000
...
二进制的角度很容易理解吧,至于里面的数学规律,我就不继续想了...
为什么不考虑8的倍数?2的倍数呢?
能力值:
(RANK:420 )
12 楼
上传的附件:
能力值:
( LV4,RANK:50 )
13 楼
很感兴趣,但是感觉理论性太强,感觉高深。
不知道哪位可以用简单的应用做例子?
以前我认为软件里的XOR跟没加密一样 - 其实是因为算法可以直接跟踪。
但是,在实际应用里,给你一段XOR之后的密文及部分明文,要求反推算法,就蒙了。
因为,这时候没有程序的算法可以让你跟踪 - 纯粹是部分密文及部分明文,这时候成了文字算法游戏了。
对这种情况,上面对XOR的讨论能给与帮助吗?
现实中,有很多这样脱离程序 - 或者我们无法跟踪内存运行的程序,比如网站上的加密 -我们不可能去调试服务器上的程序。
我希望多举点大家感兴趣的应用实例,因为太理论化,不太好懂,呵呵,谢谢大家的讨论,哪位继续给点指教一并谢谢了。 很希望哪位帮助指点一下:
在知道部分密文及部分明文的情况下,逆向XOR算法有没有什么简便些的通用方法?
以前尝试过用暴力逆推的方法,就是类似于从0到最大整数逐个推演,但是感觉不通用,有时会误入歧途。 ----------------
感谢rockinuk的回复,我想可能我发错地方了,所以转贴调试论坛了,呵呵。
这里不太适合我这种实用主义者讨论的地方,谢谢你的书单,也感叹各位的高深。
能力值:
(RANK:420 )
14 楼