Jump to content
  • Hello visitors, welcome to the Hacker World Forum!

    Red Team 1949  (formerly CHT Attack and Defense Team) In this rapidly changing Internet era, we maintain our original intention and create the best community to jointly exchange network technologies. You can obtain hacker attack and defense skills and knowledge in the forum, or you can join our Telegram communication group to discuss and communicate in real time. All kinds of advertisements are prohibited in the forum. Please register as a registered user to check our usage and privacy policy. Thank you for your cooperation.

    TheHackerWorld Official

C语言位运算符:与、或、异或、取反、左移与右移

 Share


NedK7

Recommended Posts

 

  位运算是指按二进制进行的运算。在系统软件中,常常需要处理二进制位的问题。C语言提供了6个位操作运算符,这些运算只能用于整型操作数,即只能用于带符号或无符号的char、short、int与long类型。浮点数因为浮点型和整型在计算机内的存储方式大相径庭,同样是32位。但是浮点数是1位表示符号位,23位表示数值部分,8位其他表示指数部分。而整型只是单纯32位补码形式存放的,这就是位运算不能用于浮点数的原因。
1、“按位与”运算符(&)
  按位与是指:参加运算的两个数据,按二进制进行“与”运算。如果两个相应的二进制位都位1,则该位的结果为1;否则为0。这里的1的可以理解为逻辑中的true,0可以理解为逻辑的false。按位与其实与逻辑上“与”的运算规则一致。逻辑上的“与”,要求运算数全真,结果才为真。若A=true, B=true,则A∩B=true 例如:3&5, 3的二进制编码是11(2)。(为了区分十进制和其他进制,本文规定,凡是非十进制的数据均在数据后面加上括号,括号中注明其进制,二进制则标记为2,内存储存数据的基本单位是字节(Byte),一个字节由8个位(bit)所组成。位是用以描述电脑数据量的最小单位。二进制系统中,每个0或1就是一个位。将11(2)补足成一个字节,则是00000011(2)。5的二进制编码是101(2),将其补足称一个字节,则00000101(2)。
按位与运算:
0000 0011(2) & 000000101(2) = 00000001(2)
由此可知3&5 = 1。

C语言代码:

1 #include <stdio.h>
2 
3 int main(void) {
4     int a = 3, b = 5;
5     printf("a and b: %d\n", a & b); //0011 & 0101
6     return 0;
7 }

CPU处理位运算的速度是最快的,所以很多操作我们都可以转换为位运算,以下是用按位与替换取模运算进行奇偶数判断。

 1 /*************************************************************************
 2     > File Name: 2.test.c
 3     > Author: yudongqun
 4     > Mail: [email protected]
 5     > Created Time: Sun 18 Oct 2020 10:19:55 PM CST
 6  ************************************************************************/
 7 #include <stdio.h>   
 8                         
 9 int main(void) {        
10     int n;              
11     printf("please input a integer:");
12     while (scanf("%d", &n) != EOF) {
13         //if(n % 2) {
14         if (n & 1) {                                                                                                                  
15            printf("Odd number\n"); //奇数
16         } else {        
17           printf("Even number\n");//偶数
18         }               
19         printf("please input a integer:");
20     }                   
21     return 0;           
22 } 

编译运行,并输入数字来测试,结果如下:

ydqun@VM-0-9-ubuntu 20201017 % g++ 2.test.c                                                                                       [0]
ydqun@VM-0-9-ubuntu 20201017 % ./a.out                                                                                            [0]
please input a integer:3
Odd number
please input a integer:2
Even number
please input a integer:%                                                                                                              
ydqun@VM-0-9-ubuntu 20201017 %    

14行就是用&运算符去代替%运算符实现奇偶数判断,这样效率更快。

2.按位或运算符 

两个相应的二进制位中只要有一个为1,该位的结果值为1。借用逻辑学中或运算的话来说就是,一真为真。

例如 十进制6对应二进制0000 0110与8对应的二进制0000 1000进行或运算,0000 0110 | 0000 1000 = 0000 1110,对应十进制的14。

测试的c语言代码。

 1 /*************************************************************************
 2     > File Name: 3.test.c
 3     > Author: yudongqun
 4     > Mail: [email protected]
 5     > Created Time: Mon 19 Oct 2020 05:14:44 PM CST
 6  ************************************************************************/
 7 
 8 #include <stdio.h>
 9 
10 int main(void) {
11     int n = 8, m = 6;
12     printf("%d | %d = %d\n", n, m, n | m);
13     return 0;
14 }

3.异或运算 

    异或是一个数学运算,用于逻辑运算。如果a、b两个值不同,则异或结果为1,否则结果为0,在C语言中是一种强大的基本运算符,有很多巧妙的应用。

例如, A = 14, B = 10;

A = 14,二进制则为1110,B = 10,二进制为1010.

对二进制数进行异或运算 -> 1110^1010 = 0100,对应十进制就为4。

在二进制数异或过程中,我们可以得知异或运算是一种半加运算。什么意思呢?半加即不带进位的加法运算。

如上面1110^1010 = 0100,如果在加法中,如下

  1870130-20201016164302584-331369116.png

 我们从低位开始加起,首先第0位为0+0=0;第一位1+1=0,如果是加号运算符,则需要进位,但由于是异或运算(半加),故不用进位,第二位为1+0=1;最后一位为1+1=0。最终结果就是0100,这就是半加的过程。

特性

  1.一个数与0进行异或运算,其运算结果是自身;

  2.一个数与自身进行异或运算,其运算结果为0;

  3.异或运算满足分配律,即 3^4^3与3^3^4的结果一样,都为4。

异或运算的一些应用

1.异或最常用的一种用法 -- 交换两个数的值。

  这里直接上代码。

 1 /*************************************************************************
 2     > File Name: swap.c
 3     > Author: yudongqun
 4     > Mail: [email protected]
 5     > Created Time: Fri 16 Oct 2020 04:48:54 PM CST
 6  ************************************************************************/
 7 
 8 #include <stdio.h>
 9 
10 int main(void) {
11     int a = 10, b = 20, tmp;
12 
13 #if 0
14     /*用中间值来实现值交换*/
15     tmp = a;
16     a = b;
17     b = tmp;
18 #else
19     /*用异或操作来实现值交换*/
20     a ^= b;
21     b ^= a;
22     a ^= b;
23 #endif
24     printf("a: %d, b: %d\n", a, b);
25 
26     return 0;
27 }
ydqun@VM-0-9-ubuntu operator % gcc swap.c                                                                  [0]
ydqun@VM-0-9-ubuntu operator % ./a.out                                                                     [0]
a: 20, b: 10
ydqun@VM-0-9-ubuntu operator %

这里异或操作实现的值交换的好处是少使用了一个临时变量,执行效率也比较高。

2,寻找只出现一次的数字。

给定一个非空整数数组,除了某个元素只出现一次以外,其余每个元素均出现两次。找出那个只出现了一次的元素。

说明:

你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗?

示例 1:

输入: [2,2,1]
输出: 1

示例 2:

输入: [4,1,2,1,2]
输出: 4
 1 /*************************************************************************
 2     > File Name: single_number.c
 3     > Author: yudongqun
 4     > Mail: [email protected]
 5     > Created Time: Fri 16 Oct 2020 05:20:25 PM CST
 6  ************************************************************************/
 7 
 8 #include <stdio.h>
 9 
10 int single_number(int nums[], int n) {
11     int res = 0;
12     for (int index = 0; index < n; index++) {
13         res ^= nums[index];
14     }
15     return res;
16 }
17 
18 int main(void) {
19     int nums[5] = {1, 2, 2, 1, 6};
20     printf("single number is : %d\n", single_number(nums, 5));
21 }
ydqun@VM-0-9-ubuntu operator % g++ single_number.c                                                         [0]
ydqun@VM-0-9-ubuntu operator % ./a.out                                                                     [0]
single number is : 6
ydqun@VM-0-9-ubuntu operator %  

这里是运用了异或的特性2与特性3,1^2^2^1^6 = 1^1^2^2^6 = 0^0^6 = 6。

Link to post
Link to comment
Share on other sites

 Share

discussion group

discussion group

    You don't have permission to chat.
    • Recently Browsing   0 members

      • No registered users viewing this page.
    ×
    ×
    • Create New...