算法位运算
A. 算法：使用位运算判断两个数是否同为正，或同为负
示例没有错，如果符号相反，那么异或之后所得数字符号为肯定为1，其他的非符号为取值可为0，可为1，那么此时得出的相异或的结果肯定是一个小于0的数据（最大为-1），反之如果符号相同，则符号为为0，最小为0，比较结果返回布尔值。示例代码没错的
B. 位运算可以实现什么（加减乘除等除外）
位运算只是一种比加减乘除更简单的运算，和分支循环完全没关系，很多加密解密算法，或者操作硬件的代码中，位运算是必不可少的
你用位运算对比逻辑门电路也是可以的，从这个角度看当然位运算可以实现一切，但是要全列举出来就很麻烦，相当于实现一个虚拟机，计算机软件概念是分层的，第1层实现了第2层，你可以用第2层去类比第1层然后实现第3层，但没法用第2层去直接实现第2层，除非是用基本功能去实现冗余功能，但if是基本功能之一，当然也可以利用第1层的漏洞，在第2层侵入第1层，借此影响第1层而实现第2层的基本功能，比如黑客经常利用的堆栈溢出漏洞，但这种方法不是通常意义的“实现”
C. 位运算的运算说明
=== 1. and运算 ===
and运算通常用于二进制取位操作，例如一个数 and 1的结果就是取二进制的最末位。这可以用来判断一个整数的奇偶，二进制的最末位为0表示该数为偶数，最末位为1表示该数为奇数。
相同位的两个数字都为1，则为1；若有一个不为1，则为0。
00101
11100
（&；或者and）
----------------
00100
=== 2. or运算 ===
or运算通常用于二进制特定位上的无条件赋值，例如一个数or 1的结果就是把二进制最末位强行变成1。如果需要把二进制最末位变成0，对这个数or 1之后再减一就可以了，其实际意义就是把这个数强行变成最接近的偶数。
相同位只要一个为1即为1。
00101
11100
（|或者or）
----------------
11101
=== 3. xor运算 ===
异或的符号是^。按位异或运算, 对等长二进制模式按位或二进制数的每一位执行逻辑按位异或操作. 操作的结果是如果某位不同则该位为1, 否则该位为0.
xor运算的逆运算是它本身，也就是说两次异或同一个数最后结果不变，即（a xor b) xor b = a。xor运算可以用于简单的加密，比如我想对我MM说1314520，但怕别人知道，于是双方约定拿我的生日19880516作为密钥。1314520 xor 19880516 = 20665500，我就把20665500告诉MM。MM再次计算20665500 xor 19880516的值，得到1314520，于是她就明白了我的企图。
相同位不同则为1，相同则为0。
00101
11100
（^或者xor）
----------------
11001
运算结果
x <- x # y
y <- x @ y
x <- x @ y
执行了第一句后x变成了x # y。那么第二句实质就是y <- x # y @ y，由于#和@互为逆运算，那么此时的y变成了原来的x。第三句中x实际上被赋值为（x # y) @ x，如果#运算具有交换律，那么赋值后x就变成最初的y了。这三句话的结果是，x和y的位置互换了。
加法和减法互为逆运算，并且加法满足交换律。把#换成+，把@换成-，我们可以写出一个不需要临时变量的swap过程（Pascal）。
procere swap(var a,b:longint);
begin
a:=a + b;
b:=a - b;
a:=a - b;
end;
好了，刚才不是说xor的逆运算是它本身吗？于是我们就有了一个看起来非常诡异的swap过程：
procere swap(var a,b:longint);
begin
a:=a xor b;
b:=a xor b;
a:=a xor b;
end;
注意：位运算版本的交换两数不适用于一个数的自我交换。也就是说，如果上述程序的“b”改成“a”的话，其结果是变量a变成零。因此，在使用快速排序时，由于涉及到一个数的自我交换，因此如果要在其中使用位运算版的交换两数的话，应该先判断。具体的时间损耗在此略过。
=== 4. not运算 ===
not运算的定义是把内存中的0和1全部取反。使用not运算时要格外小心，你需要注意整数类型有没有符号。如果not的对象是无符号整数（不能表示负数），那么得到的值就是它与该类型上界的差，因为无符号类型的数是用00到$FFFF依次表示的。下面的两个程序（仅语言不同）均返回65435。
var
a:word;
begin
a:=100;
a:=not a;
writeln(a);
end. #include<stdio.h>intmain(){unsignedshorta=100;a=~a;printf(%d
,a);return0;}如果not的对象是有符号的整数，情况就不一样了，稍后我们会在“整数类型的储存”小节中提到。
=== 5. shl运算 ===
a shl b就表示把a转为二进制后左移b位（在后面添b个0）。例如100的二进制为1100100，而110010000转成十进制是400，那么100 shl 2 = 400。可以看出，a shl b的值实际上就是a乘以2的b次方，因为在二进制数后添一个0就相当于该数乘以2。
通常认为a shl 1比a * 2更快，因为前者是更底层一些的操作。因此程序中乘以2的操作请尽量用左移一位来代替。
定义一些常量可能会用到shl运算。你可以方便地用1 shl 16 - 1来表示65535。很多算法和数据结构要求数据规模必须是2的幂，此时可以用shl来定义Max_N等常量。
=== 6. shr运算 ===
和shl相似，a shr b表示二进制右移b位（去掉末b位），相当于a除以2的b次方（取整）。我们也经常用shr 1来代替div 2，比如二分查找、堆的插入操作等等。想办法用shr代替除法运算可以使程序效率大大提高。最大公约数的二进制算法用除以2操作来代替慢得出奇的mod运算，效率可以提高60%。
D. 什么是位运算
位，它是什么？你可能会问。
简单来说，位就是1和0，在电脑中做的每一件事都是由它们组成的。电脑中所有的数据使用的是位。一个字节由8个位组成；一个字由两个字节组成，即16个位；而一个双字由四个字节组成，即32个位。
0 1 0 0 0 1 1 1 1 0 0 0 0 1 1 1 0 1 1 1 0 1 0 0 0 1 1 1 1 0 0 0
||..............|...............|...............|..............||
|+- bit 31......|...............|...............|.......bit 0 -+|
|...............|...............|...............|...............|
+-- BYTE 3 -----+--- BYTE 2 ----+--- BYTE 1 ----+-- BYTE 0 -----+
|...............................|...............................|
+----------- WORD 1 ------------+----------- WORD 0 ------------+
|...............................................................|
+--------------------------- DWORD -----------------------------+
使用字节，字或者双字来进行位操作显得比较美观，就像使用一个小型数组或结构。使用位运算，可以检查或设置单独某一位的值或组位的值。
十六进制数和位的关系
人们发现，使用二进制计数法表示数字比较的困难。为避免这一问题，采用十六进制计数法（基数为16）。十六进制的一位数字从0到15分别用二进制的四位来表示。四位一组，即半字节。一个字节有两个半字节，则可以用两位十六进制数表示一个字节的值。
半字节 十六进制数
====== =========
0000........0
0001........1
0010........2
0011........3
0100........4
0101........5
0110........6
0111........7
1000........8
1001........9
1010........A
1011........B
1100........C
1101........D
1110........E
1111........F
如果有一个字节，内容为字母‘r’（ASCII 码 114），则表示如下：
0111 0010 二进制数
7 2 十六进制数
记为：0x72
位运算符
共有6种位运算符，如下：
& 与运算符
| 或运算符
^ 异或运算符
~ 取反运算符
>> 右移运算符
<< 左移运算符
& 运算符
&（与）运算要求有两个运算值，然后返回一个值，当且仅当两个运算值都位1时，返回值为1。如下表：
1 & 1 == 1
1 & 0 == 0
0 & 1 == 0
0 & 0 == 0
一个字节可以包含位标志，而使用与运算可以通过设置掩码来检查某位的值。算法如下：它用来判断字节中的第四位是否为1
BYTE b = 50;
if ( b & 0x10 )
cout << "Bit four is set" << endl;
else
cout << "Bit four is clear" << endl;
通过以下计算可以得到结果：
....00110010 - b
& 00010000 - & 0x10
----------
....00010000 - result
所以，第四位为1。
| 运算符
|（或）运算符要求两个运算值，然后返回一个值，当且仅当两个运算值中有一个为1或都为1时，返回值为1。如下表：
1 | 1 == 1
1 | 0 == 1
0 | 1 == 1
0 | 0 == 0
使用或运算可以保证字节中的某位为1。算法如下：它用来保证第二位总是为1
BYTE b = 50;
BYTE c = b | 0x04;
cout << "c = " << c << endl;
通过以下计算可以得到结果：
....00110010 - b
| 00000100 - | 0x04
----------
....00110110 - result
^ 异或运算符
^ （异或）运算符要求有两个运算值，然后返回一个值，当且仅当两个运算值中有一个为1但不同时为1时，返回值为1。如下表：
1 ^ 1 == 0
1 ^ 0 == 1
0 ^ 1 == 1
0 ^ 0 == 0
使用异或运算可以翻转特定的位。即0变1，1变0。算法如下：翻转第三和第四位
BYTE b = 50;
cout << "b = " << b << endl;
b = b ^ 0x18;
cout << "b = " << b << endl;
b = b ^ 0x18;
cout << "b = " << b << endl;
通过以下计算可以得到结果：
....00110010 - b
^ 00011000 - ^ 0x18
----------
....00101010 - result
00101010 - b
^ 00011000 - ^ 0x18
----------
....00110010 - result
~ 取反运算符
~（取反）运算符只要求一个运算值，然后将所有的1变成0，所有的0变成1。使用取反运算可以将某些字节置0，确保其它字节置1，而不用考虑
数据的大小。算法如下：将所有位置1，而第一和第零位置0
BYTE b = ~0x03;
cout << "b = " << b << endl;
WORD w = ~0x03;
cout << "w = " << w << endl;
通过以下计算可以得到结果：
00000011 - 0x03
11111100 - ~0x03 b
0000000000000011 - 0x03
1111111111111100 - ~0x03 w
同&（与）运算符一起使用，可以使任意位置0。算法如下：将第四位置0
BYTE b = 50;
cout << "b = " << b << endl;
BYTE c = b & ~0x10;
cout << "c = " << c << endl;
通过以下计算可以得到结果：
....00110010 - b
& 11101111 - ~0x10
----------
....00100010 - result
>>和<< 右移和左移运算符
>>（右移）运算符和<<（左移）运算符将数据右移或左移若干位。>>右移运算从高位往低位移，<<左移运算从低位往高位移。
BYTE b = 12;
cout << "b = " << b << endl;
BYTE c = b << 2;
cout << "c = " << c << endl;
c = b >> 2;
cout << "c = " << c << endl;
通过以下计算可以得到结果：
00001100 - b
00110000 - b << 2
00000011 - b >> 2
位段
位段是位运算中比较令人感兴趣的部分。使用位段可以在一个字节，字或双字内设置小型结构。例如：要记录日期，要求尽可能少的使用内存，则可以采用如下的结构申明：
struct date_struct {
BYTE day : 5, // 1 to 31
month : 4, // 1 to 12
year : 14; // 0 to 9999
} date;
在上面的例子中，日占据了最低的5位，月份占据了接下来的4位，年份为接下来的14位。则整个日期储存在三个字节的23位中。第二十四位被忽略。如果使用整形申明则将占据12个字节。
|0 0 0 0 0 0 0 0|0 0 0 0 0 0 0 0|0 0 0 0 0 0 0 0|
| | | |
+------ year ---------------+ month +-- day --+
如上所述，date类型使用的位段结构。这里使用的是BYTE。一BYTE为8位，使用的时候，编译器将申请一个BYTE来储存。如果结构超过8位，编译器将再申请一个BYTE，直到足够用来储存结构。如果使用字或双字，编译器将总共申请32位用来储存结构。
怎样申明位段？首先申明位段变量，跟着冒号，然后是分配给变量的位数；每位段用逗号分隔，最后用分号表示申明结束。
完成结构申明后，则可以通过存取标记方便的使用结构，同时也可以使用地址操作符使用结构的地址对结构进行操作。如下：
date.day = 12;
dateptr = &date;
dateptr->year = 1852;
E. 有哪些有趣而且神奇的按位运算
1) 判断int型变量a是奇数还是偶数
a&1 = 0 偶数
a&1 = 1 奇数
(2) 取int型变量a的第k位 (k=0,1,2……sizeof(int))，即a>>k&1 (先右移再与1)
(3) 将int型变量a的第k位清0，即a=a&~(1<<k) (10000 取反后为00001 )
(4) 将int型变量a的第k位置1，即a=a|(1<<k)
(5) int型变量循环左移k次，即a=a<<k|a>>16-k (设sizeof(int)=16)
(6) int型变量a循环右移k次，即a=a>>k|a<<16-k (设sizeof(int)=16)
(7)整数的平均值
对于两个整数x,y，如果用 (x+y)/2 求平均值，会产生溢出，因为 x+y 可能会大于INT_MAX，但是我们知道它们的平均值是肯定不会溢出的，我们用如下算法：
int average(int x, int y) //返回X、Y的平均值
{
return (x & y) + ( (x^y)>>1 );
}
(8)对于一个数 x >= 0，判断是不是2的幂。
boolean power2(int x)
{
return ( (x&(x-1))==0) && (x!=0);
}
(9)不用temp交换两个整数
void swap(int x , int y)
{
x ^= y;
y ^= x;
x ^= y;
}
(10)计算绝对值
int abs( int x )
{
int y ;
y = x >> 31 ;
return (x^y)-y ; //or: (x+y)^y
}
(11)取模运算转化成位运算 (在不产生溢出的情况下)
a % (2^n) 等价于 a & (2^n - 1)
(12)乘法运算转化成位运算 (在不产生溢出的情况下)
a * (2^n) 等价于 a<< n
(13)除法运算转化成位运算 (在不产生溢出的情况下)
a / (2^n) 等价于 a>> n
例: 12/8 == 12>>3
(14) a % 2 等价于 a & 1
(15) if (x == a)
x= b;
else
x= a;
等价于 x= a ^ b ^ x;
(16) x 的 相反数 表示为 (~x+1)
(17)输入2的n次方：1 << 19
(18)乘除2的倍数：千万不要用乘除法，非常拖效率。只要知道左移1位就是乘以2，右移1位就是除以2就行了。比如要算25 * 4，用25 << 2就好啦。
F. C语言 位运算
按照位运算，0跟1相与和0跟0相与为0，1跟1相与为1。
根据这个算法，假设a有16位，某种情况下只需要后8位，前八位归0，就可以采用与0000000011111111这个16位数字相与，因为a的前八位不管是0还是1，与0相与都化为零，后八位不管是0还是1，与1相与还是原数。也就是所说的”把数值a的高八位清零，保留低八位“
G. 什么是位运算它的主要功能是什么 试描述选择排序法与冒泡排序法的算法及区别。
位运算现将操作数各对应的二进位进行具体的与或非等操作，常用来对特定位清零或置1等。
冒泡排序通常在待排序数组基本有序的情况下使用，而且考得比较多。