❶ c語言中取反運算符'"!"如何使用
運算符"!"是邏輯非運算符;"~"才是按位取反運算符。
經過"!"運算後,運算結果只有0或1;而經過"~"運算後,結果有多種,取決於操作數。
下面通過實例來介紹這個運算符的使用方法:
inta=10,b,c;
b=!a;//運算後b=0,因為a不等於0(即為真),所以取非後等於0(為假)
c=~a;//運算後c=5,因為a的二進制位1010,按位取反後變為0101(即等於5)
❷ C語言 按位取反
2的二進制: 0000 0010
-2的二進制:1111 1110
~-2: 0000 0001
負數的二進製表示方法:第一位符號位,然後取無符號部分取反後加1,得出負數的二進製表示。
❸ C語言位運算題目
#include<stdio.h>
intmain()
{
inta,k;
scanf("%x%d",&a,&k);
printf("%#x",a^(1<<k-1));
return0;
}
❹ c語言,按位取反。
題目有問題 如果是 ~16= -17 的話就是這樣
0001 0000 = 16
~16 = 1110 1111 (計算機內存中就是這樣的,補碼)
1110 1111 = 1001 0001 (補碼轉換源碼就是等於 -17,將補碼全部取反 +1 (注意最前面的1是符號位,不能省去))
如果不要符號位的話 就全部有效 (一個個乘下去 ) 有符號位 前面的1就代表負數
❺ c語言中的位運算符中『按位取反』是怎麼運算的
使用~按位取反運算的時候,計算機會將操作數所對應的二進製表達式的每一個位進行取反計算,取反後所得到的值就是~按位取反的運算結果。
例如,假如計算機是32位的,接下來要計算~5的值,計算過程如下:
5 的二進製表達式為:0000 0000 0000 0000 0000 0000 0000 0101
執行~運算,即~5後: 1111 1111 1111 1111 1111 1111 1111 1010,即結果為-6
以上過程沒有任何問題,但如果忘記了負數的二進製表達方式,那麼就會對這個結果產生疑問,為什麼1111 1111 1111 1111 1111 1111 1111 1010表示-6,可能會以為它應該表示-10等等,所以,使用~按位取反的另一個關鍵就是理解1111 1111 1111 1111 1111 1111 1111 1010為什麼表示-6,也即理解負數的二進製表達方式。
(5)c語言k位取反擴展閱讀
js取整
~是按位取反運算,~~是取反兩次
在這里~~的作用是去掉小數部分
因為位運算的操作值要求是整數,其結果也是整數,所以經過位運算的都會自動變成整數
除了~~n 還可以用
n<<0
n>>0
n|0
❻ C語言中的位運算符是怎麼取反的
~1010的反碼是0101
而負數在計算機中的表示是用補碼,-11求補碼過程:1011取反->0100加1->0101
即-11等價於~10
括弧中的是0101
補充說明:是這樣的,1010在32位計算機中的存儲實際上是00001010,取反後是11110101,在計算機中首位是0表示正數,是1表示負數,即11110101表示的是一個負數,即要由11110101求這個負數,即求補碼的逆,步驟:先減1得11110100,再取反,取反時符號位不變,得10001011,即-11。用4位表示的話可以填0101,或者是8位的11110101
❼ 關於c語言按位取反的運算
兩者都為1為1,否則為0。
1&1=1,1&0=0,0&1=0,0&0=0
或運算:|
兩者都為0為0,否則為1
1|1=1,1|0=1,0|1=1,0|0=0
非運算:~
1取0,0取1
~1=0,~0=1
~(10001)=01110
異或運算
兩者相等為0,不等為1
1^1=0,1^0=1,0^1=1,0^0=0
(7)c語言k位取反擴展閱讀:
位運算符有:
&(按位與)、|(按位或)、^(按位異或)、~(按位取反)。
其中,按位取反運算符是單目運算符,其餘均為雙目運算符。
位運算符的優先順序從高到低,依次為~、&、^、|,
其中~的結合方向自右至左,且優先順序高於算術運算符,其餘運算符的結合方向都是自左至右,且優先順序低於關系運算符。
❽ C語言,哪位好心的大哥,姐姐:能告述我位運算嗎我看不懂啊!
位運算簡介及實用技巧(一):基礎篇
什麼是位運算?
程序中的所有數在計算機內存中都是以二進制的形式儲存的。位運算說穿了,就是直接對整數在內存中的二進制位進行操作。比如,and運算本來是一個邏輯運算符,但整數與整數之間也可以進行and運算。舉個例子,6的二進制是110,11的二進制是1011,那麼6 and 11的結果就是2,它是二進制對應位進行邏輯運算的結果(0表示False,1表示True,空位都當0處理):
110
AND 1011
---------------
0010 --> 2
由於位運算直接對內存數據進行操作,不需要轉成十進制,因此處理速度非常快。當然有人會說,這個快了有什麼用,計算6 and 11沒有什麼實際意義啊。這一系列的文章就將告訴你,位運算到底可以干什麼,有些什麼經典應用,以及如何用位運算優化你的程序。
Pascal和C中的位運算符號
下面的a和b都是整數類型,則:
C語言 | Pascal語言
-------+-------------
a & b | a and b
a | b | a or b
a ^ b | a xor b
~a | not a
a << b| a shl b
a >> b | a shr b
注意C中的邏輯運算和位運算符號是不同的。520|1314=1834,但520||1314=1,因為邏輯運算時520和1314都相當於True。同樣的,!a和~a也是有區別的。
各種位運算的使用
=== 1. and運算 ===
and運算通常用於二進製取位操作,例如一個數 and 1的結果就是取二進制的最末位。這可以用來判斷一個整數的奇偶,二進制的最末位為0表示該數為偶數,最末位為1表示該數為奇數.
=== 2. or運算 ===
or運算通常用於二進制特定位上的無條件賦值,例如一個數or 1的結果就是把二進制最末位強行變成1。如果需要把二進制最末位變成0,對這個數or 1之後再減一就可以了,其實際意義就是把這個數強行變成最接近的偶數。
=== 3. xor運算 ===
xor運算通常用於對二進制的特定一位進行取反操作,因為異或可以這樣定義:0和1異或0都不變,異或1則取反。
xor運算的逆運算是它本身,也就是說兩次異或同一個數最後結果不變,即(a xor b) xor b = a。xor運算可以用於簡單的加密,比如我想對我MM說1314520,但怕別人知道,於是雙方約定拿我的生日19880516作為密鑰。1314520 xor 19880516 = 20665500,我就把20665500告訴MM。MM再次計算20665500 xor 19880516的值,得到1314520,於是她就明白了我的企圖。
下面我們看另外一個東西。定義兩個符號#和@(我怎麼找不到那個圈裡有個叉的字元),這兩個符號互為逆運算,也就是說(x # y) @ y = x。現在依次執行下面三條命令,結果是什麼?
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;
=== 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>
int main()
{
unsigned short a=100;
a = ~a;
printf( "%d\n", a );
return 0;
}
如果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%。
位運算的簡單應用
有時我們的程序需要一個規模不大的Hash表來記錄狀態。比如,做數獨時我們需要27個Hash表來統計每一行、每一列和每一個小九宮格里已經有哪些數了。此時,我們可以用27個小於2^9的整數進行記錄。例如,一個只填了2和5的小九宮格就用數字18表示(二進制為000010010),而某一行的狀態為511則表示這一行已經填滿。需要改變狀態時我們不需要把這個數轉成二進制修改後再轉回去,而是直接進行位操作。在搜索時,把狀態表示成整數可以更好地進行判重等操作。這道題是在搜索中使用位運算加速的經典例子。以後我們會看到更多的例子。
下面列舉了一些常見的二進制位的變換操作。
功能 | 示例 | 位運算
----------------------+---------------------------+--------------------
去掉最後一位 | (101101->10110) | x shr 1
在最後加一個0 | (101101->1011010) | x shl 1
在最後加一個1 | (101101->1011011) | x shl 1+1
把最後一位變成1 | (101100->101101) | x or 1
把最後一位變成0 | (101101->101100) | x or 1-1
最後一位取反 | (101101->101100) | x xor 1
把右數第k位變成1 | (101001->101101,k=3) | x or (1 shl (k-1))
把右數第k位變成0 | (101101->101001,k=3) | x and not (1 shl (k-1))
右數第k位取反 | (101001->101101,k=3) | x xor (1 shl (k-1))
取末三位 | (1101101->101) | x and 7
取末k位 | (1101101->1101,k=5) | x and (1 shl k-1)
取右數第k位 | (1101101->1,k=4) | x shr (k-1) and 1
把末k位變成1 | (101001->101111,k=4) | x or (1 shl k-1)
末k位取反 | (101001->100110,k=4) | x xor (1 shl k-1)
把右邊連續的1變成0 | (100101111->100100000) | x and (x+1)
把右起第一個0變成1 | (100101111->100111111) | x or (x+1)
把右邊連續的0變成1 | (11011000->11011111) | x or (x-1)
取右邊連續的1 | (100101111->1111) | (x xor (x+1)) shr 1
去掉右起第一個1的左邊 | (100101000->1000) | x and (x xor (x-1))
最後這一個在樹狀數組中會用到。
Pascal和C中的16進製表示
Pascal中需要在16進制數前加$符號表示,C中需要在前面加0x來表示。這個以後我們會經常用到。
整數類型的儲存
我們前面所說的位運算都沒有涉及負數,都假設這些運算是在unsigned/word類型(只能表示正數的整型)上進行操作。但計算機如何處理有正負符號的整數類型呢?下面兩個程序都是考察16位整數的儲存方式(只是語言不同)。
var
a,b:integer;
begin
a:=00;
b:=01;
write(a,' ',b,' ');
a:=$FFFE;
b:=$FFFF;
write(a,' ',b,' ');
a:=FFF;
b:=00;
writeln(a,' ',b);
end.
#include <stdio.h>
int main()
{
short int a, b;
a = 0x0000;
b = 0x0001;
printf( "%d %d ", a, b );
a = 0xFFFE;
b = 0xFFFF;
printf( "%d %d ", a, b );
a = 0x7FFF;
b = 0x8000;
printf( "%d %d\n", a, b );
return 0;
}
兩個程序的輸出均為0 1 -2 -1 32767 -32768。其中前兩個數是內存值最小的時候,中間兩個數則是內存值最大的時候,最後輸出的兩個數是正數與負數的分界處。由此你可以清楚地看到計算機是如何儲存一個整數的:計算機用00到FFF依次表示0到32767的數,剩下的00到$FFFF依次表示-32768到-1的數。32位有符號整數的儲存方式也是類似的。稍加註意你會發現,二進制的第一位是用來表示正負號的,0表示正,1表示負。這里有一個問題:0本來既不是正數,也不是負數,但它佔用了00的位置,因此有符號的整數類型範圍中正數個數比負數少一個。對一個有符號的數進行not運算後,最高位的變化將導致正負顛倒,並且數的絕對值會差1。也就是說,not a實際上等於-a-1。這種整數儲存方式叫做「補碼」。
位運算簡介及實用技巧(二):進階篇(1)
===== 真正強的東西來了! =====
二進制中的1有奇數個還是偶數個
我們可以用下面的代碼來計算一個32位整數的二進制中1的個數的奇偶性,當輸入數據的二進製表示里有偶數個數字1時程序輸出0,有奇數個則輸出1。例如,1314520的二進制101000000111011011000中有9個1,則x=1314520時程序輸出1。
var
i,x,c:longint;
begin
readln(x);
c:=0;
for i:=1 to 32 do
begin
c:=c + x and 1;
x:=x shr 1;
end;
writeln( c and 1 );
end.
但這樣的效率並不高,位運算的神奇之處還沒有體現出來。
同樣是判斷二進制中1的個數的奇偶性,下面這段代碼就強了。你能看出這個代碼的原理嗎?
var
x:longint;
begin
readln(x);
x:=x xor (x shr 1);
x:=x xor (x shr 2);
x:=x xor (x shr 4);
x:=x xor (x shr 8);
x:=x xor (x shr 16);
writeln(x and 1);
end.
為了說明上面這段代碼的原理,我們還是拿1314520出來說事。1314520的二進制為101000000111011011000,第一次異或操作的結果如下:
XOR
---------------------------------------
得到的結果是一個新的二進制數,其中右起第i位上的數表示原數中第i和i+1位上有奇數個1還是偶數個1。比如,最右邊那個0表示原數末兩位有偶數個1,右起第3位上的1就表示原數的這個位置和前一個位置中有奇數個1。對這個數進行第二次異或的結果如下:
XOR
---------------------------------------
結果里的每個1表示原數的該位置及其前面三個位置中共有奇數個1,每個0就表示原數對應的四個位置上共偶數個1。一直做到第五次異或結束後,得到的二進制數的最末位就表示整個32位數里有多少個1,這就是我們最終想要的答案。
計算二進制中的1的個數
同樣假設x是一個32位整數。經過下面五次賦值後,x的值就是原數的二進製表示中數字1的個數。比如,初始時x為1314520(網友抓狂:能不能換一個數啊),那麼最後x就變成了9,它表示1314520的二進制中有9個1。
x := (x and 555555) + ((x shr 1) and 555555);
x := (x and 333333) + ((x shr 2) and 333333);
x := (x and F0F0F0F) + ((x shr 4) and F0F0F0F);
x := (x and FF00FF) + ((x shr 8) and FF00FF);
x := (x and 00FFFF) + ((x shr 16) and 00FFFF);
為了便於解說,我們下面僅說明這個程序是如何對一個8位整數進行處理的。我們拿數字211(我們班某MM的生日)來開刀。211的二進制為11010011。
+---+---+---+---+---+---+---+---+
| 1 | 1 | 0 | 1 | 0 | 0 | 1 | 1 | <---原數
+---+---+---+---+---+---+---+---+
| 1 0 | 0 1 | 0 0 | 1 0 | <---第一次運算後
+-------+-------+-------+-------+
| 0 0 1 1 | 0 0 1 0 | <---第二次運算後
+---------------+---------------+
| 0 0 0 0 0 1 0 1 | <---第三次運算後,得數為5
+-------------------------------+
整個程序是一個分治的思想。第一次我們把每相鄰的兩位加起來,得到每兩位里1的個數,比如前兩位10就表示原數的前兩位有2個1。第二次我們繼續兩兩相加,10+01=11,00+10=10,得到的結果是00110010,它表示原數前4位有3個1,末4位有2個1。最後一次我們把0011和0010加起來,得到的就是整個二進制中1的個數。程序中巧妙地使用取位和右移,比如第二行中333333的二進制為00110011001100....,用它和x做and運算就相當於以2為單位間隔取數。shr的作用就是讓加法運算的相同數位對齊。
二分查找32位整數的前導0個數
這里用的C語言,我直接Copy的Hacker's Delight上的代碼。這段代碼寫成C要好看些,寫成Pascal的話會出現很多begin和end,搞得代碼很難看。程序思想是二分查找,應該很簡單,我就不細說了。
int nlz(unsigned x)
{
int n;
if (x == 0) return(32);
n = 1;
if ((x >> 16) == 0) {n = n +16; x = x <<16;}
if ((x >> 24) == 0) {n = n + 8; x = x << 8;}
if ((x >> 28) == 0) {n = n + 4; x = x << 4;}
if ((x >> 30) == 0) {n = n + 2; x = x << 2;}
n = n - (x >> 31);
return n;
}
只用位運算來取絕對值
這是一個非常有趣的問題。大家先自己想想吧,Ctrl+A顯示答案。
答案:假設x為32位整數,則x xor (not (x shr 31) + 1) + x shr 31的結果是x的絕對值
x shr 31是二進制的最高位,它用來表示x的符號。如果它為0(x為正),則not (x shr 31) + 1等於000000,異或任何數結果都不變;如果最高位為1(x為負),則not (x shr 31) + 1等於$FFFFFFFF,x異或它相當於所有數位取反,異或完後再加一。
高低位交換
這個題實際上是我出的,做為學校內部NOIp模擬賽的第一題。題目是這樣:
給出一個小於2^32的正整數。這個數可以用一個32位的二進制數表示(不足32位用0補足)。我們稱這個二進制數的前16位為「高位」,後16位為「低位」。將它的高低位交換,我們可以得到一個新的數。試問這個新的數是多少(用十進製表示)。
例如,數1314520用二進製表示為0000 0000 0001 0100 0000 1110 1101 1000(添加了11個前導0補足為32位),其中前16位為高位,即0000 0000 0001 0100;後16位為低位,即0000 1110 1101 1000。將它的高低位進行交換,我們得到了一個新的二進制數0000 1110 1101 1000 0000 0000 0001 0100。它即是十進制的249036820。
當時幾乎沒有人想到用一句位操作來代替冗長的程序。使用位運算的話兩句話就完了。
var
n:dword;
begin
readln( n );
writeln( (n shr 16) or (n shl 16) );
end.
而事實上,Pascal有一個系統函數swap直接就可以用。
二進制逆序
下面的程序讀入一個32位整數並輸出它的二進制倒序後所表示的數。
輸入: 1314520 (二進制為)
輸出: 460335104 (二進制為)
var
x:dword;
begin
readln(x);
x := (x and 555555) shl 1 or (x and $AAAAAAAA) shr 1;
x := (x and 333333) shl 2 or (x and $CCCCCCCC) shr 2;
x := (x and F0F0F0F) shl 4 or (x and $F0F0F0F0) shr 4;
x := (x and FF00FF) shl 8 or (x and $FF00FF00) shr 8;
x := (x and 00FFFF) shl 16 or (x and $FFFF0000) shr 16;
writeln(x);
end.
它的原理和剛才求二進制中1的個數那個例題是大致相同的。程序首先交換每相鄰兩位上的數,以後把互相交換過的數看成一個整體,繼續進行以2位為單位、以4位為單位的左右對換操作。我們再次用8位整數211來演示程序執行過程:
+---+---+---+---+---+---+---+---+
| 1 | 1 | 0 | 1 | 0 | 0 | 1 | 1 | <---原數
+---+---+---+---+---+---+---+---+
| 1 1 | 1 0 | 0 0 | 1 1 | <---第一次運算後
+-------+-------+-------+-------+
| 1 0 1 1 | 1 1 0 0 | <---第二次運算後
+---------------+---------------+
| 1 1 0 0 1 0 1 1 | <---第三次運算後
+-------------------------------+
位運算簡介及實用技巧(三):進階篇(2)
今天我們來看兩個稍微復雜一點的例子。
n皇後問題位運算版
n皇後問題是啥我就不說了吧,學編程的肯定都見過。下面的十多行代碼是n皇後問題的一個高效位運算程序,看到過的人都誇它牛。初始時,upperlim:=(1 shl n)-1。主程序調用test(0,0,0)後sum的值就是n皇後總的解數。拿這個去交USACO,0.3s,暴爽。
procere test(row,ld,rd:longint);
var
pos,p:longint;
begin
if row<>upperlim then
begin
pos:=upperlim and not (row or ld or rd);
while pos<>0 do
begin
p:=pos and -pos;
pos:=pos-p;
test(row+p,(ld+p)shl 1,(rd+p)shr 1);
end;
end
else inc(sum);
end;
乍一看似乎完全摸不著頭腦,實際上整個程序是非常容易理解的。這里還是建議大家自己單步運行一探究竟,實在沒研究出來再看下面的解說。
和普通演算法一樣,這是一個遞歸過程,程序一行一行地尋找可以放皇後的地方。過程帶三個參數,row、ld和rd,分別表示在縱列和兩個對角線方向的限制條件下這一行的哪些地方不能放。我們以6x6的棋盤為例,看看程序是怎麼工作的。假設現在已經遞歸到第四層,前三層放的子已經標在左圖上了。紅色、藍色和綠色的線分別表示三個方向上有沖突的位置,位於該行上的沖突位置就用row、ld和rd中的1來表示。把它們三個並起來,得到該行所有的禁位,取反後就得到所有可以放的位置(用pos來表示)。前面說過-a相當於not a + 1,這里的代碼第6行就相當於pos and (not pos + 1),其結果是取出最右邊的那個1。這樣,p就表示該行的某個可以放子的位置,把它從pos中移除並遞歸調用test過程。注意遞歸調用時三個參數的變化,每個參數都加上了一個禁位,但兩個對角線方向的禁位對下一行的影響需要平移一位。最後,如果遞歸到某個時候發現row=111111了,說明六個皇後全放進去了,此時程序從第1行跳到第11行,找到的解的個數加一。
~~~~====~~~~===== 華麗的分割線 =====~~~~====~~~~
Gray碼
假如我有4個潛在的GF,我需要決定最終到底和誰在一起。一個簡單的辦法就是,依次和每個MM交往一段時間,最後選擇給我帶來的「滿意度」最大的MM。但看了dd牛的理論後,事情開始變得復雜了:我可以選擇和多個MM在一起。這樣,需要考核的狀態變成了2^4=16種(當然包括0000這一狀態,因為我有可能是玻璃)。現在的問題就是,我應該用什麼順序來遍歷這16種狀態呢?
傳統的做法是,用二進制數的順序來遍歷所有可能的組合。也就是說,我需要以0000->0001->0010->0011->0100->...->1111這樣的順序對每種狀態進行測試。這個順序很不科學,很多時候狀態的轉移都很耗時。比如從0111到1000時我需要暫時甩掉當前所有的3個MM,然後去把第4個MM。同時改變所有MM與我的關系是一件何等巨大的工程啊。因此,我希望知道,是否有一種方法可以使得,從沒有MM這一狀態出發,每次只改變我和一個MM的關系(追或者甩),15次操作後恰好遍歷完所有可能的組合(最終狀態不一定是1111)。大家自己先試一試看行不行。
解決這個問題的方法很巧妙。我們來說明,假如我們已經知道了n=2時的合法遍歷順序,我們如何得到n=3的遍歷順序。顯然,n=2的遍歷順序如下:
00
01
11
10
你可能已經想到了如何把上面的遍歷順序擴展到n=3的情況。n=3時一共有8種狀態,其中前面4個把n=2的遍歷順序照搬下來,然後把它們對稱翻折下去並在最前面加上1作為後面4個狀態:
000
001
011
010 ↑
--------
110 ↓
111
101
100