コンピュータの中の数はバイナリの形式で記憶して演算して、各ビットは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))

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であることを示すことができる

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に等しい数は0 x 0と0 x 1億円で0を除外すればよい!(x+1+x+1)&!(x+1)デバッグ時エラー、0 xffと0 x 0 x 0以外の定数を使用して、0 xffと0 x 0変換から0 x 1 0 xff+0 xff=0 x 1 fe 0 x 1 fe&0 xff=0 xfe 0 xfe^0 xff=0 x 1

// 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ビットのバイナリ数の16進法は0 xaaaaaと表すxが奇数ビットを満たしてすべて1であれば、逆の奇数ビットを取ってすべて0であればx&0 xaaaaaaaのすべてのビットは0である

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

negate

return -x Example: negate(1) = -1. Legal ops: ! ~ & ^ | + << >> Max ops: 5 Rating: 2
1つの数の反対数の補符号は、その数の逆符号に1を加算することを表す

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が0 x 30~0 x 39 x-0 x 30のシンボルビットが0 x-0 x 3 aのシンボルビットが1

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
0 xffffffff&a=a,0 x 00000000&b=0 x 00000000 x=1 x=1の場合、0 xffffff(0)が得られ、x=0の場合、0 x 00000000(1)が得られる.x-1つまり!x+~1+1

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);
}

考え方2:シフト

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

xがyと同じ番号の場合、p=y-x>=0に変換され、pシンボルビット(p>>31)&1が0の場合、1が返され、シンボルビット1は0が返される.

異号の場合、x>=0であれば0を返し、そうでなければ1を返し、(x>>31)&1で判断する.

c=a+bはx,y同号か異号かの判断とすることができる.

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のシンボルビットを考慮する.

x=0 x 0のとき、x,yの両方のシンボルビットは0である.

x=0 x 8000 0000の場合、x,yの両方のシンボルビットは1である.

でなければ、両者のシンボルビットは01または10である.

は、離散数学の真値テーブルから(x)&(y)を導出し、x=0x0のみの場合、そのシンボルビットは1

である.

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

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

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

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

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
分割して、まず、2ビットの場合、例えばバイナリ10、10&01は最低ビットが1であるか否かを示し、(x>>1)&1は最低ビットのゼロビットが1であるか否かを示し、(x&0 x 1)+(x>>1)&0 x 1は各ビットの1の個数を計算し、加算する

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

次に、4ビットの場合、例えば10011001&0101=001、(1001>>1)&0101=001を考慮する.0001+0100=0101は2桁ごとに1つずつあることを示し、4桁を2段2桁の2桁の2桁の2桁の2桁の2桁の数と見なし、1段ごとの1の個数は1つの2桁の2桁の2桁の2桁の2桁の数で0101&0011=001を表す.(0101>>2)=0001,0001&0011=0001; 2桁ごとに1の個数を計算し、0001+0001=0100を加算すると、最後の答えになります.

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;
}

次に、8ビットの場合、例えば、0111100101111001&01010101=010000101111001>>1=0111100を考慮する.00101100&01010101=00010100,00010100+01010001=01100101; 2ビットごとにそれぞれ1,2,1,1があり、次に4ビットごとの1の個数01100101&0010011=010000101100101>>2=00010011を計算する.00100001+00010001=00010010010 4ビットごとにそれぞれ3があり、2つの1は次に8ビットごとに1の個数を計算する

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ビットの計算は以下のように普及した.

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;
}