位运算之按位与

文章目录

按位与的概念

1.按位与,两个都为1则为1,有一个0就是0
2.无论是0还是1只要和1与上之后,都保持不变
3.无论是0还是1只要和0与上之后,就变成0
4.在c语言中,前缀0b代表2进制数,如0b001,前导0可有可无

1.判断奇偶性

1
2
3
4
5
6
7
8
9
10
11
12
13
int main()
{
int c = 3;
if (c & 0b1)//前导0b代表他是2进制数,最后1和任何数按位,都是得最后一个数
{
printf("奇数");//最后一位为1就是奇数
}
else
{
printf("偶数");
}
return 0;
}

2.保留最后5个数

1
2
3
4
5
6
int main()
{
int c = 0b1001000;
printf("%d", c & 0b11111);//和1按为就会保留那些,保留最后5个数
return 0;
}

消除最后4个数

1
2
3
4
5
6
7
8
转化成16进制方便
int main()
{
int c = 0b1101011;
//前面都为1,后4个都为0即可
printf("%d", c&0xfffffff0);
return 0;
}

2 的幂

2 的幂

给你一个整数 n,请你判断该整数是否是 2 的幂次方。如果是,返回 true ;否则,返回 false 。

如果存在一个整数 x 使得 n == 2x ,则认为 n 是 2 的幂次方。

示例 1:

输入:n = 1 输出:true 解释:20 = 1

示例 2:

输入:n = 16 输出:true 解释:24 = 16

示例 3:

输入:n = 3 输出:false

示例 4:

输入:n = 4 输出:true

示例 5:

输入:n = 5 输出:false

提示:

1
-231 <= n <= 231 - 1

判断是否是2的幂 2的幂一定是10000,有1个1,后面全是0 所以判断条件是x-1为011111,两者与一下全变成了0

1
2
3
4
5

bool isPowerOfTwo(int n){

return n>0&&(n&(n-1))==0;//当n大于0才会有2的幂次方,小于等于0都是错的
}

2进制数中位1的个数

位1的个数

编写一个函数,输入是一个无符号整数(以二进制串的形式),返回其二进制表达式中数字位数为 ‘1’ 的个数(也被称为汉明重量)。

提示:

1
2
请注意,在某些语言(如 Java)中,没有无符号整数类型。在这种情况下,输入和输出都将被指定为有符号整数类型,并且不应影响您的实现,因为无论整数是有符号的还是无符号的,其内部的二进制表示形式都是相同的。
Java 中,编译器使用二进制补码记法来表示有符号整数。因此,在上面的 示例 3 中,输入表示有符号整数 -3

示例 1:

输入:00000000000000000000000000001011 输出:3 解释:输入的二进制串
00000000000000000000000000001011 中,共有三位为 ‘1’。

示例 2:

输入:00000000000000000000000010000000 输出:1 解释:输入的二进制串
00000000000000000000000010000000 中,共有一位为 ‘1’。

示例 3:

输入:11111111111111111111111111111101 输出:31 解释:输入的二进制串
11111111111111111111111111111101 中,共有 31 位为 ‘1’。

提示:

1
输入必须是长度为 32 的 二进制串 。
1
2
3
4
5
6
7
8
9
int hammingWeight(uint32_t n) {
int cnt=0;
while(n)//消到最后都变成了0
{
n&=(n-1);//每次都把最高位的1给消掉了,消完之后到了下一个1的位置,执行的次数就是1的个数
cnt++;
}
return cnt;
}

二进制表示中质数个计算置位

二进制表示中质数个计算置位

给定两个整数 L 和 R ,找到闭区间 [L, R] 范围内,计算置位位数为质数的整数个数。

(注意,计算置位代表二进制表示中1的个数。例如 21 的二进制表示 10101 有 3 个计算置位。还有,1 不是质数。)

示例 1:

输入: L = 6, R = 10 输出: 4 解释: 6 -> 110 (2 个计算置位,2 是质数) 7 -> 111 (3
个计算置位,3 是质数) 9 -> 1001 (2 个计算置位,2 是质数) 10-> 1010 (2 个计算置位,2 是质数)

示例 2:

输入: L = 10, R = 15 输出: 5 解释: 10 -> 1010 (2 个计算置位, 2 是质数) 11 -> 1011 (3
个计算置位, 3 是质数) 12 -> 1100 (2 个计算置位, 2 是质数) 13 -> 1101 (3 个计算置位, 3 是质数)
14 -> 1110 (3 个计算置位, 3 是质数) 15 -> 1111 (4 个计算置位, 4 不是质数)

注意:

1
2
L, R 是 L <= R 且在 [1, 10^6] 中的整数。
R - L 的最大值为 10000
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
int numbers(int x)
{
int cnt=0;
while(x)
{
x&=(x-1);
cnt++;
}
return cnt;
}
bool isprime(int x)
{
int i;
if(x==0||x==1)
{
return false;
}
for(i=2;i<=(x/i);i++)
{
if(x%i==0)
{
return false;
}
}
return true;
}
int countPrimeSetBits(int left, int right){
//写一个计算1的个数,写一个判断个数是否为奇数
int n=0;
int i;
for(i=left;i<=right;i++)
{
if(isprime(numbers(i)))
{
n++;
}
}
return n;

}

根据数字二进制下 1 的数目排序

根据数字二进制下 1 的数目排序

给你一个整数数组 arr 。请你将数组中的元素按照其二进制表示中数字 1 的数目升序排序。

如果存在多个数字二进制中 1 的数目相同,则必须将它们按照数值大小升序排列。

请你返回排序后的数组。

示例 1:

输入:arr = [0,1,2,3,4,5,6,7,8] 输出:[0,1,2,4,8,3,5,6,7] 解释:[0] 是唯一一个有 0 个
1 的数。 [1,2,4,8] 都有 1 个 1 。 [3,5,6] 有 2 个 1 。 [7] 有 3 个 1 。 按照 1
的个数排序得到的结果数组为 [0,1,2,4,8,3,5,6,7]

示例 2:

输入:arr = [1024,512,256,128,64,32,16,8,4,2,1]
输出:[1,2,4,8,16,32,64,128,256,512,1024] 解释:数组中所有整数二进制下都只有 1 个 1
,所以你需要按照数值大小将它们排序。

示例 3:

输入:arr = [10000,10000] 输出:[10000,10000]

示例 4:

输入:arr = [2,3,5,7,11,13,17,19] 输出:[2,3,5,17,7,11,13,19]

示例 5:

输入:arr = [10,100,1000,10000] 输出:[10,100,10000,1000]

提示:

1
2
1 <= arr.length <= 500
0 <= arr[i] <= 10^4
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
/**
* Note: The returned array must be malloced, assume caller calls free().
*/
int hammingWeight(uint32_t n) {
int cnt=0;
while(n)//消到最后都变成了0
{
n&=(n-1);//每次都把最高位的1给消掉了,消完之后到了下一个1的位置,执行的次数就是1的个数
cnt++;
}
return cnt;
}
void swap(int *a,int *b)
{
int tmp=*a;
*a=*b;
*b=tmp;
}
int* sortByBits(int* arr, int arrSize, int* returnSize) {
//先写一个计算1的个数
//安1的个数进行排序
//已经升序
//
int *cnt = (int *)malloc(sizeof(int)*arrSize);
int i = 0;
*returnSize = arrSize;
for (i = 0; i < arrSize; i++)
{
cnt[i] = hammingWeight(arr[i]);
}
int j=0;
for(i=0;i<arrSize-1;i++)
{
for(j=0;j<arrSize-1-i;j++)
{
if(cnt[j]>cnt[j+1])
{
swap(&arr[j],&arr[j+1]);
swap(&cnt[j],&cnt[j+1]);//按照1的个数排完序了,现在按大小排
}
}
}
for(i=0;i<arrSize-1;i++)
{
for(j=0;j<arrSize-1-i;j++)
{
if(cnt[j]==cnt[j+1]&&arr[j]>arr[j+1])
{
swap(&arr[j],&arr[j+1]);
//按照1的个数排完序了,现在按大小排
}
}
}
int *ret=(int*)malloc(sizeof(int)*arrSize);
for(i=0;i<arrSize;i++)
{
ret[i]=arr[i];
}
return ret;

}

位运算之按位与
http://example.com/2021/12/17/位运算之按位与/
作者
Zevin
发布于
2021年12月17日
许可协议