datalab

发表于 分类于

计算机中的数以二进制的形式存储和运算，每个比特不是0就是1。计算机通过对比特进行不同方式的编码和描述，从而执行纷繁复杂的各种任务。我们有诸多基于底层的接口，所以一般不会直接接触到比特的运算。datalab直接与编码数字序列的0和1打交道，通过对整数和浮点数的位操作来实现一系列的操作。

整数运算

bitXor

x^y using only ~ and &
Example: bitXor(4, 5) = 1
Legal ops: ~ &
Max ops: 14
Rating: 1

假设a,b均为由单个二进制位表示的数
则a,b,a^b对应真值表如下
a^b在a,b中只有一个取1时取1

a b a^b
0 1 1
1 1 0
1 0 1
0 0 1

(a&b)|(b&a)
a取0，b取1时为1，
b取0，a取1时为1，
((a&b)|(b&a))即为结果
但是只能用和&，化简得(((a)&b))&(((b)&a))

1
2
3
int bitXor(int x, int y) {
  return (~((~x)&y))&(~((~y)&x));
}

tmin

return minimum two’s complement integer
Legal ops: ! ~ & ^ | + << >>
Max ops: 4
Rating: 1

32位时补码可以表示最大整数为1>>31

1
2
3
int tmin(void) {
 return 1>>31;
}

isTmax

returns 1 if x is the maximum, two’s complement number,and 0 otherwise
Legal ops: ! ~ & ^ | +
Max ops: 10
Rating: 1

2(Tmax+1)会溢出为0，符合2*num等于0的数只有0x0和0x10000000
再排除0即可
!(x+1+x+1)&!(x+1)
调试时报错，不可以使用0xff和0x0以外的常数，由0xff和0x0变换得到0x1
0xff+0xff=0x1fe
0x1fe&0xff=0xfe
0xfe^0xff=0x1

1
2
3
4
5
//以下的tmp即为0x1;
 int isTmax(int x) {
   tmp=((0xff+0xff)&0xff)^0xff;
  return !(x+tmp+x+tmp)&!(x+tmp);
}

allOddBits

return 1 if all odd-numbered bits in word set to 1
where bits are numbered from 0 (least significant) to 31 (most significant)
Examples allOddBits(0xFFFFFFFD) = 0, allOddBits(0xAAAAAAAA) = 1
Legal ops: ! ~ & ^ | + << >>
Max ops: 12
Rating: 2

奇数位全为0，偶数位全为1的32位二进制数的十六进制表示为0xaaaaaaaa
若x满足奇数位全为1，则取反后奇数位全为0
则x&0xaaaaaaaa所有位均为0

1
2
3
int allOddBits(int x) {
  return !(~x&0xaaaaaaaa);
}

negate

return -x
Example: negate(1) = -1.
Legal ops: ! ~ & ^ | + << >>
Max ops: 5
Rating: 2

一个数的相反数的补码表示为该数的反码再加一

1
2
3
4
5
x+~x=0xffffffff=-1
x+~x+1=0
int negate(int x) {
  return (~x+1);
}

isAsciiDigit

return 1 if 0x30 <= x <= 0x39 (ASCII codes for characters ‘0’ to ‘9’)
Example: isAsciiDigit(0x35) = 1.
isAsciiDigit(0x3a) = 0.
isAsciiDigit(0x05) = 0.
Legal ops: ! ~ & ^ | + << >>
Max ops: 15
Rating: 3

判断x在0x30到0x39
x-0x30的符号位为0
x-0x3a的符号位为1

1
2
3
int isAsciiDigit(int x) {
  return (!((x+(~(0x30)+1))>>31))&((x+(~(0x3A)+1))>>31);
}

conditional

same as x ? y : z
Example: conditional(2,4,5) = 4
Legal ops: ! ~ & ^ | + << >>
Max ops: 16
Rating: 3

0xffffffff&a=a,0x00000000&b=0x00000000
当x=1时，得到0xffffffff(0),当x=0时，得到0x00000000(1)
思路一：!x-1 也即!x+~1+1

1
2
3
4
5
6
7
int conditional(int x, int y, int z) {
  cond=!x+~1+1
  return (mask&y)|((~mask&z);
}
int conditional(int x, int y, int z) {
  return ((!x+~1+1)&y)|((~!x+1)&z);
}

思路二：位移

1
2
3
4
int conditional(int x, int y, int z) {
  mask=(x>>31)<<31;
  return (mask&y)|(~mask&z);
}

isLessOrEqual

if x <= y then return 1, else return 0
Example: isLessOrEqual(4,5) = 1.
Legal ops: ! ~ & ^ | + << >>
Max ops: 24
Rating: 3

  1. 在x与y同号的情况下转换为p=y-x>=0，然后p符号位(p>>31）&1为0则返回1，符号位1则返回0；
  2. 异号时，只要x>=0，就要返回0，否则返回1，由(x>>31)&1判断；
  3. c=a+b可作为x,y同号还是异号的判断。
1
2
3
4
5
6
7
8
9
int isLessOrEqual(int x, int y) {
  int a=x>>31;
  int b=y>>31;
  int c=a^b;
  int p=y+(~x+1);
  int q=!((p>>31)&1);
  int ans=(c&q)|(!c&a);
  return ans;
}

logicalNeg

implement the ! operator, using all of the legal operators except !
Examples: logicalNeg(3) = 0, logicalNeg(0) = 1
Legal ops: ~ & ^ | + << >>
Max ops: 12
Rating: 4

令y=~x+1，考虑x与y的符号位：

  1. 当x=0x0时，x，y两者符号位都为0；
  2. 当x=0x8000 0000时，x，y两者符号位都为1；
  3. 否则，两者符号位为01或10；
  4. 根据离散数学的真值表得出(x)&(y)，则当且仅当x=0x0时，其符号位为1
1
2
3
int logicalNeg(int x) {
  return ((~(~x+1)&~x)>>31)&1;
}

howManyBits

return the minimum number of bits required to represent x in two’s complement
Examples: howManyBits(12) = 5
howManyBits(298) = 10
howManyBits(-5) = 4
howManyBits(0) = 1
howManyBits(-1) = 1
howManyBits(0x80000000) = 32
Legal ops: ! ~ & ^ | + << >>
Max ops: 90
Rating: 4

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
int howManyBits(int x) {
	int temp=x^(x>>31);//x小于0时取反码
    int isZero=!temp;
    //notZeroMask is 0xffffffff
    int notZeroMask=(!(!temp)<<31)>>31;
    int bit_16,bit_8,bit_4,bit_2,bit_1;
    bit_16=!(!(temp>>16))<<4;
    //see if the high 16bits have value,if have,then we need at least 16 bits
    //if the highest 16 bits have value,then rightshift 16 to see the exact place of  
    //if not means they are all zero,right shift nothing and we should only consider the low 16 bits
    temp=temp>>bit_16;
    bit_8=!(!(temp>>8))<<3;
    temp=temp>>bit_8;
    bit_4=!(!(temp>>4))<<2;
    temp=temp>>bit_4;
    bit_2=!(!(temp>>2))<<1;
    temp=temp>>bit_2;
    bit_1=!(!(temp>>1));
    temp=bit_16+bit_8+bit_4+bit_2+bit_1+2;//at least we need one bit for 1 to tmax,
    //and we need another bit for sign
    return isZero|(temp&notZeroMask);
}

浮点数运算

floatScale2

Return bit-level equivalent of expression 2*f for
floating point argument f.
Both the argument and result are passed as unsigned int’s, but they are to be interpreted as the bit-level representation of
single-precision floating point values.
When argument is NaN, return argument
Legal ops: Any integer/unsigned operations incl. ||, &&. also if, while
Max ops: 30
Rating: 4

1
2
3
4
5
6
7
8
9
10
11
12
13
14
unsigned floatScale2(unsigned uf) {
  unsigned s = uf&0x80000000;
	unsigned exp = uf&0x7f800000;
	unsigned frac = uf&0x007fffff;
	if(!exp) {
		frac<<=1;
	}else if(exp^0x7f800000) {
		exp += 0x00800000;
		if(!(exp^0x7f800000)) {
			frac = 0;
		}
	}
	return s|exp|frac;
}

floatFloat2Int

Return bit-level equivalent of expression (int) f
for floating point argument f.
Argument is passed as unsigned int, but it is to be interpreted as the bit-level representation of a
single-precision floating point value.
Anything out of range (including NaN and infinity) should return 0x80000000u.
Legal ops: Any integer/unsigned operations incl. ||, &&. also if, while
Max ops: 30
Rating: 4

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
int floatFloat2Int(unsigned uf) {
  int sign=(uf>>31)&1;//取得符号位
  int exp=uf>>23&0xff;//取得阶码
  int frac=uf&0x7fffffff;//取得小数位
  int E=exp-127;//计算E
  if(exp==255||E>30){
    return 0x80000000u;//如果超出表示范围，返回0x80000000u
  }
  else if(!exp||E<0) {
    return 0;//如果exp为0或偏移量小于0，均为不大于1的小数，E均等于1，则舍入到0
  }
  frac=frac|(1<<23);//frac=frac+1.0
  //小数点在23位处，根据E与23的相对位置调整小数点
  if (E>23){
    frac=frac<<(E-23);
  } else {
    frac=frac>>(23-E);
  }
  if (sign) {
    frac = ~(frac) + 1;
  }
  return frac;
}

float_i2f

Return bit-level equivalent of expression (float) x
Result is returned as unsigned int, but it is to be interpreted as the bit-levelrepresentation of a single-precision floating point values.
Legal ops: Any integer/unsigned operationsincl. ||, &&. also if, while
Max ops: 30
Rating: 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
unsigned float_i2f_2(int x) {  
    int sign = x>>31&1; 
    int i;  
    int exponent;   
    int fraction; 
    int delta;  
    int fraction_mask;  
    if(x == 0)  
        return x;  
    else if(x==0x80000000)  
        exponent=158; //x为Tmin(-2^31)时,exponent=31+127=158 
    else{  
        if (sign)  
            x = -x;  
        i = 30;  
        while ( !(x >> i) )  
            i--;//小数点偏移位数  
        exponent = i + 127;
        x = x << (31 - i);  
        fraction_mask = 0x7fffff;  
        fraction = fraction_mask & (x >> 8);//32位数字舍弃低八位和首位的1得到23位的小数域
		
        x = x & 0xff; //舍入部分 
        delta = x > 128 || ((x == 128) && (fraction & 1));//向偶数舍入
		
        fraction += delta;  
        if(fraction >> 23) {  
            fraction &= fraction_mask;//处理溢出情况  
            exponent += 1;  
        }  
    }  
    return (sign<<31)|(exponent<<23)|fraction;  
}

bitCount

returns count of number of 1’s in word
Examples: bitCount(5) = 2, bitCount(7) = 3
Legal ops: ! ~ & ^ | + << >>
Max ops: 40
Rating: 4

分而治之，首先我们考虑两位的情况
例如二进制10,10&01表明最低位是否为1，(x>>1)&1,表明最低位的零位是否为1，
(x&0x1)+(x>>1)&0x1
计算每一位中1的个数并且相加

1
2
3
4
5
int bitcount2(int x)
{
    int bit1=0x1;
    return x&bit1+(x>>1)&bit1;
}

接下来我们考虑四位的情况
例如1001，1001&0101=0001,(1001>>1)&0101=0001;
0001+0100=0101表示每两位均各有1个1，
将四位看作两段两位的二进制数，每段的1的个数由一个二位二进制数表示
0101&0011=0001；(0101>>2)=0001,0001&0011=0001;
计算每两位中1的个数并且相加
0001+0001=0010,即为最后的答案

1
2
3
4
5
6
7
8
int bitcount4(int x)
{
    int mask1=0x1;
    int mask2=0x3;
    int ans=(x&mask1)+(x>>1)&mask1;
    ans=(ans&mask2)+(ans>>2)&mask2;
    return ans;
}

接下来我们考虑八位的情况
例如01111001，01111001&01010101=01010001,01111001>>1=00111100;
00101100&01010101=00010100,00010100+01010001=01100101;
每二位分别有1，2，1，1个1
接下来计算每四位中1的个数
01100101&00110011=00100001，01100101>>2=00011001;
00100001+00010001=00110010
每四位分别有3，2个1
接下来计算每8位中1的个数

1
2
3
4
5
6
7
8
9
int bitcount8(int x)
{
    int mask1=0x55;
    int mask2=0x33;
    int mask3=0x0f;
    int ans=(x&mask1)+((x>>1)&mask1);
    ans=(ans&mask2)+((ans>>2)&mask2);
    ans=(ans&mask3)+((ans>>4)&mask3);
}

推广得到32位的计算如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int bitCount(int x) {
  int _mask1 = (0x55)|(0x55<<8);
  int _mask2 = (0x33)|(0x33<<8);
  int _mask3 = (0x0f)|(0x0f<<8);
  int mask1 = _mask1|(_mask1<<16);
  int mask2 = _mask2|(_mask2<<16);
  int mask3 = _mask3|(_mask3<<16);
  int mask4 = (0xff)|(0xff<<16);
  int mask5 = (0xff)|(0xff<<8);

  int ans = (x & mask1) + ((x>>1) & mask1);
  ans = (ans & mask2) + ((ans>>2) & mask2);
  ans = (ans & mask3) + ((ans>>4) & mask3);
  ans = (ans & mask4) + ((ans>>8) & mask4);
  ans = (ans & mask5) + ((ans>>16) & mask5);

  return ans;
}