演算法位運算
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等。
冒泡排序通常在待排序數組基本有序的情況下使用，而且考得比較多。