C and bit and Tree array
站长
· 阅读数 8
一个int -2147483648 2147483647 它是4个字节 32bit
二进制：{0，1}
十进制: {0,......,9}
0x 十六进制: {0,........9,A,B,C,D,E,F}
16 = 2^4 也就是所 4bit的二进制 = 1bit的十六进制
0x FFFF FFFF = -1 0x 7FFF FFFF =2147483647
开始快乐的code的之旅
#include<stdlib.h>
#include<stdio.h>
//32位
int main(){
printf("Hello world\n",);//格式化打印
return 0; //正常退出
//return 1; 有错误
}
那我们怎么运行这个程序呢？
cmd下进入这个文件所在的目录
gcc test.c -o x //编译 -o 就是编译成可执行文件 x便是你生成的文件的名字
dir //查看
2021/08/26 22:05 562 C语言、位操作、树状数组.md
2021/08/26 22:09 173 test.c
2021/08/26 22:09 132,611 x.exe
你会发现生成了一个x.exe
x //输入文件名执行
C:\Users\Shuaikb\Desktop\15213>x
Hello world
//输出
#include<stdlib.h>
#include<stdio.h>
//32位
int main(){
int a = 123;
printf("%d\n",a); //格式化打印
//%d整数占位符
return 0; //正常退出
}
\n 是换行符
#include<stdlib.h>
#include<stdio.h>
//32位
int main(){
int a = 2147483647;
printf("%d\n",a+1); //格式化打印
//%d整数占位符
return 0; //正常退出
}
C:\Users\Shuaikb\Desktop\15213>test
-2147483648
如果我们的a是inte能表示的最大整数呢？
与或非
非门：0 -> 1 1 -> 0 ~ //取反
与门：0x0=0 1x0=0 1x1=1 0x1=1 & //整数乘法 有0就是0
或门：0+0=0 1+0=1 0+1=1 1+1=1 | //整数加法 有1就是1
异或：0x0=0 0x1=1 1x0=1 1x1=0 ^ //相同为1 不同为0 或的基础上 1x1 =0
int a = 1;
int b = 3;
int 是32位 因为我们这里数太小前面 3个字节都是0 就省略不写了
a =0000 0001
~a =1111 1110 +1
=1111 1111
~a + 1 = -1 //a取反+1 就是它的负数
C:\Users\Shuaikb\Desktop\15213>test
-1
a&b = 1 //a与b
a =0000 0001
b =0000 0011 //与是整数乘法
=0000 0001
C:\Users\Shuaikb\Desktop\15213>test
1
a|b //a或b
a =0000 0001
b =0000 0011 //或是整数加法
=0000 0011
C:\Users\Shuaikb\Desktop\15213>test
3
a^b //a异或b
a =0000 0001
b =0000 0011 //异或是在或的基础上 1x1 =0
=0000 0010
C:\Users\Shuaikb\Desktop\15213>test
2
注意最大时负数是 1111 1111 = -1
最小的负数是 1000 0000 =-128
unsigned LowBit(unsigned x){
unsigned a = 0;
//怎么我们才能让a = 1000
a = x & ( (~x) + 1);
return a;
}
//32位
int main(){
printf("0x%x\n", LowBit(0xffffffff)); //格式化打印
//%d整数占位符
return 0; //正常退出
}
0xffffffff = 11111111
~ = 00000000
+1 = 00000001
x& = 00000001
= 00000001 =1
C:\Users\Shuaikb\Desktop\15213>test
0x1
C语言中 %X的意思是以十六进制数形式输出整数
unsigned LowBit(unsigned x){
unsigned a = 0;
//怎么我们才能让a = 1000
a = x & ( (~x) + 1);
return a;
}
//32位
int main(){
//a = 10 = 1010
printf("0x%x\n", LowBit(0xa)); //格式化打印
//%d整数占位符
return 0; //正常退出
}
0xffffffff = 00001010
~ = 11110101
+1 = 11110110
x& = 00000010
= 00000010 =2
C:\Users\Shuaikb\Desktop\15213>test
0x2
这个lowbit可以取出最低的出现1的地方
xxxx xxx1 // x
yyyy yyy0 //取反
yyyy yyy1 //+1 = -x
x与y永远是下相反的 所有 x&y = 0
树状数组
0
0 0
0 0 0 0
0 0 0 0 0 0 0 0
1 2 3 4 5 6 7 8
s1 s2 s3 s4 s5 s3 s4 s8
你从上往下看只能看到涂黑的球
Si //就是树状数组
Ti //就是线段树
S7 = a1 + ... +a7 //它总能表示成若干个T数组的和
= T4 + T6 + T7
你会发现上面操作了 7次 下面只用操作3次
上面是 O(n) 下面是O(logN)
unsigned LowBit(unsigned x){
unsigned a = 0;
//怎么我们才能让a = 1000
a = x & ( (~x) + 1);
return a;
}
//32位
int main(){
//
unsigned n = 7;
printf("S[%u]=\n",n);
printf(" T[%u]\n", n);
n = n - LowBit(n);
printf("+ T[%u]\n",n);
n = n - LowBit(n);
printf("+ T[%u]\n", n);
n = n - LowBit(n);
printf("+ T[%u]\n", n);
return 0;
}
C:\Users\Shuaikb\Desktop\15213>test
S[7]=
T[7]
+ T[6]
+ T[4]
+ T[0]
你真的理解0x了吗？
0xabcdef123
unsigned a = ????????
判断一个数的十六进制是不是每一位都是字母
一个数 x3x2x1x0
所有为1的项都是 x3为1 且x1为1
那么可以得出 f(1) = x3 * x2+x3 * x1 = x3(x2+x1) = x3 & (x1 | x2)
对应一个32位的数 他会被分出 8个4bit
每个4bit 我们去看 x3x2x1 然后进行 x3 & (x1 | x2)
如果都是1那就能完成条件
unsigned Letter(unsigned x){
//如果你想获得x1
// x3 x2 x1 x0 -hex
// 0 0 1 0 & 0x2
// 0 0 x1 0
//每一个字节都要一个2 那就是0x22222222
//0x22222222 & a
//同理获得 x3 x2 x1
unsigned x1 = x & 0x22222222;
unsigned x2 = x & 0x44444444;
unsigned x3 = x & 0x88888888;
//x3 * (x1+x2) = x3 & (x1+x2)
//但是他们位置是错开的
//x3 1000 >>3位 0001
//x2 0100 >>2位 0001
//x1 0001 >>1位 0001
unsigned a = (x3 >> 3) & ((x2 >> 2) | (x1 >> 1));
//你会输出每一位是不是字母
return a; //a = 0 就不全是字母, a = 1 全是字母;
}
//32位
int main(){
unsigned n = 7;
printf("0x%x, is letter %x\n",0xabcdefab,Letter(0xabcdefab));
printf("0x%x, is letter %x\n",0xabcd1111,Letter(0xabcd1111));
return 0;
}
C:\Users\Shuaikb\Desktop\15213>test
0xabcdefab, is letter 11111111
0xabcd1111, is letter 11110000
转载自:https://juejin.cn/post/7001115603171803166