1.txt

bit operations 2007 version in C

 294  
 295    // There are two possible cases:
 296    // 1) when the sign of x and y are different
 297    // there will be no overflow
 298    case_1 = (!!(sign_x^sign_y));
 299   
 300    // 2) when the signs of x and y are the same
 301    // check the sign of x+y and whether it's the same as the signs of x and y
 302    case_2 = !((sign_x^sign_xpy) | (sign_y^sign_xpy));
 303    
 304    return case_1 + case_2;
 305  
 306  }
 307  /* 
 308   * rempwr2 - Compute x%(2^n), for 0 <= n <= 30
 309   *   Negative arguments should yield negative remainders
 310   *   Examples: rempwr2(15,2) = 3, rempwr2(-35,3) = -3
 311   *   Legal ops: ! ~ & ^ | + << >>
 312   *   Max ops: 20
 313   *   Rating: 3
 314   */
 315  int rempwr2(int x, int n) {
 316    
 317    // x%2^n represents all the bits right side of 2^n bit
 318  
 319    int sign_x,abs_x,remainder,negate_x,negate_rem;
 320  
 321    // First, we have to check whether x is positive or negative
 322    // if it's negative change it to positive
 323    sign_x = x>>31;
 324    negate_x = (~x)+1;
 325    abs_x = ((~sign_x)&x) + (sign_x&negate_x);
 326  
 327    // in order to make all the bits left side of 2^n to zero, we can cancel them using & and their complements
 328    remainder = abs_x&(~(abs_x^(~((~0)<<n))));
 329    negate_rem = (~remainder)+1;
 330  
 331    // if x is negative, put minus sign for the result
 332    return ((~sign_x)&remainder) + (sign_x&negate_rem);
 333  
 334  }
 335  /* 
 336   * isLess - if x < y  then return 1, else return 0 
 337   *   Example: isLess(4,5) = 1.
 338   *   Legal ops: ! ~ & ^ | + << >>
 339   *   Max ops: 24
 340   *   Rating: 3
 341   */
 342  int isLess(int x, int y) {
 343  
 344    int case_1,case_2,sign_x,sign_y,x_minus_y;
 345  
 346    sign_x = x>>31;
 347    sign_y = y>>31;
 348  
 349    // There are two different cases:
 350    // 1) when the sign of x and y are different, overflow won't happen, 
 351    // just check the sign of x and y
 352    case_1 = !((sign_x+1)^sign_y);
 353  
 354    // 2) when the sign of x and y are the same, 
 355    // overflow occurs when the sign of x+y is different from the signs of x and y
 356    // thus eliminate that option, and do x-y to check whether it's greater or less than 0
 357    x_minus_y = x+((~y)+1);
 358    case_2 = !!((~(sign_x^sign_y)) & (x_minus_y)>>31);
 359    
 360    return case_1 | case_2;
 361  
 362  }
 363  /* 
 364   * absVal - absolute value of x
 365   *   Example: absVal(-1) = 1.
 366   *   You may assume -TMax <= x <= TMax
 367   *   Legal ops: ! ~ & ^ | + << >>
 368   *   Max ops: 10
 369   *   Rating: 4
 370   */
 371  int absVal(int x) {
 372    
 373    int sign_x;
 374    int negate_x;
 375  
 376    // when x is negative, use 2's complement((~x)+1) to make it positive
 377    // when x is positive, leave it as it is
 378    sign_x = (x>>31);
 379    negate_x = (~x)+1;
 380    return (sign_x&negate_x) + ((~sign_x)&x);
 381  
 382  }
 383  /*
 384   * isPower2 - returns 1 if x is a power of 2, and 0 otherwise
 385   *   Examples: isPower2(5) = 0, isPower2(8) = 1, isPower2(0) = 0
 386   *   Note that no negative number is a power of 2.
 387   *   Legal ops: ! ~ & ^ | + << >>
 388   *   Max ops: 20
 389   *   Rating: 4
 390   */
 391  int isPower2(int x) {
 392  
 393    int case_1, case_2, case_3, negate_0;
 394  
 395    negate_0 = ~0;
 396  
 397    // Check whether x is negative: if it is, return 0
 398    case_1 = !(x>>31);
 399  
 400    // Check whether x is 0: if x is 0, then return 0
 401    case_2 = (!(x^0))+negate_0;
 402  
 403    // if x is not 0, then pass the algorithm by returning 1111....1111
 404    // if the number x is Power2, then x and x-1 do not share even a single bit which are right to the only 1-bit position of x
 405    // thus (x&(x-1)) will return 0
 406    case_3 = !(x&(x+negate_0));
 407  
 408    return case_1 & case_2 & case_3;
 409  
 410  }
 411  /* 
 412   * float_neg - Return bit-level equivalent of expression -f for
 413   *   floating point argument f.
 414   *   Both the argument and result are passed as unsigned int's, but
 415   *   they are to be interpreted as the bit-level representations of
 416   *   single-precision floating point values.
 417   *   When argument is NaN, return NaN value 0x7FC00000.
 418   *   Legal ops: Any integer/unsigned operations.  Conditional operations
 419   *   Max ops: 10
 420   *   Rating: 2
 421   */
 422  unsigned float_neg(unsigned uf) {
 423    
 424    int mantissa, exp;
 425  
 426    // Set mantissa and exponent value according to the bit representation of uf
 427    mantissa = uf&0x007fffff;
 428    exp = ((uf&0x7f800000)>>23);
 429  
 430    // if exponent is all 1s and mantissa is not zero,
 431    // by its definition, it is NaN
 432    // if it's not NaN then change the sign bit
 433    if((exp == 0x000000ff) && (mantissa != 0))
 434      return 0x7fc00000;
 435    else
 436      return uf^0x80000000;
 437  
 438  }
 439  /* 
 440   * float_half - Return bit-level equivalent of expression 0.5*f for
 441   *   floating point argument f.
 442   *   Both the argument and result are passed as unsigned int's, but
 443   *   they are to be interpreted as the bit-level representation of
 444   *   single-precision floating point values.
 445   *   When argument is NaN, return NaN value 0x7FC00000.
 446   *   Legal ops: Any integer/unsigned operations.  Conditional operations
 447   *   Max ops: 30
 448   *   Rating: 4
 449   */
 450  unsigned float_half(unsigned uf) {
 451    
 452    int mantissa, exp, rev_exp, sign, new, new_2, shift_m;
 453  
 454    // Set mantissa, exponent, and sign values
 455    mantissa = uf&0x007fffff;  
 456    exp = (uf&0x7f800000)>>23; 
 457    sign = uf&0x80000000; 
 458   
 459    // if the number is +0,-0,+infinity,or -infinity
 460    // the number divide half will be the original number
 461    if(uf == 0x7f800000)
 462      return uf;
 463    if(uf == 0xff800000)
 464      return uf;
 465    if(uf == 0)
 466      return uf;
 467    if(uf == 0x80000000)
 468      return uf;
 469  
 470    // if exponent is not zero, we can divide the number by half 
 471    // by simply decreasing the exponent value by one
 472    rev_exp = (exp-1)<<23;
 473    new = sign+rev_exp+mantissa;
 474  
 475    // if exponent is zero, we have to divide mantissa by 2
 476    new_2 = sign+(mantissa/2);
 477  
 478    // if exponent value is all 1s, and mantiss is not zero, then it's NaN
 479    if((exp == 0x000000ff) && (mantissa != 0)) 
 480      return 0x7fc00000;
 481   
 482    // if exponent value is 1, then make exponent value to 0
 483    // and right shift mantissa by one including 1-bit in MSB
 484    else if(exp == 0x00000001)
 485      { 
 486        shift_m = (uf&0x7fffffff)>>1;
 487        shift_m |= sign;
 488        
 489        // when divide mantissa by 2,
 490        // if the last two bit of mantissa is 11 before dividing, then round up 
 491        if((mantissa & 0x00000003) == 0x00000003) 
 492          return shift_m+1; 
 493        else 
 494          return shift_m; 
 495      } 
 496    else if((exp == 0) && (mantissa != 0))
 497      {
 498        // when divide mantissa by 2,
 499        // if the last two bit of mantissa is 11 before dividing, then round up
 500        if((mantissa & 0x00000003) == 0x00000003)
 501        return new_2+1;
 502      else
 503        return new_2;
 504      }
 505    else
 506      return new;
 507  
 508  }
 509  /* 
 510   * float_i2f - Return bit-level equivalent of expression (float) x
 511   *   Result is returned as unsigned int, but
 512   *   it is to be interpreted as the bit-level representation of a
 513   *   single-precision floating point values.
 514   *   Legal ops: Any integer/unsigned operations.  Conditional operations
 515   *   Max ops: 30
 516   *   Rating: 4
 517   */
 518  unsigned float_i2f(int x) {
 519  
 520    int val, val_r, n, exp, x_1, check_r, mantissa, power_2, mantissa_r;
 521  
 522    n = 0;
 523    val = 0;
 524    val_r = 0;
 525    exp = 0;
 526  
 527    // if x is negative, convert it into positive
 528    if(x<0)
 529      {
 530        val |= 0x80000000;
 531        x_1 = -x;
 532      }
 533    else if(x>0)
 534      x_1 = x;
 535    else
 536      return 0;
 537  
 538    // find the position of the most left-positioned 1-bit of x
 539    while(n != 32)
 540      {
 541        power_2 = 1<<n;
 542        if(power_2&x_1)
 543          exp = n;
 544        n += 1;
 545      }
 546  
 547    // set exponent value
 548    val |= ((exp+127)<<23);
 549  
 550    // since mantissa is always greater than or equal to 1, delete the most left-positioned 1-bit
 551    x_1 = (x_1 - (1<<exp));
 552  
 553    // if mantissa is less than or equal to 23 bit, left shift mantissa by (23-exp)
 554    if(exp <= 23)
 555      val |= (x_1<<(23-exp));
 556  
 557    // if mantissa is greater than 23 bit,
 558    
 559    else
 560      {
 561        // check_r checks the decimal places
 562        check_r = (x_1<<(55-exp));
 563  
 564        // since mantissa is greater than 23 bit, so round mantissa to 23 bit
 565        mantissa = x_1>>(exp-23);
 566  
 567        // mantissa_r is the rounded up version of mantissa
 568        mantissa_r = mantissa + 1;
 569        
 570        // val_r is the float value with mantissa_r
 571        val_r = val + mantissa_r;
 572        
 573        // if the decimal places are greater than 1/2, then round up the mantissa
 574        if((check_r > 0x80000000) && (check_r < 0x00000000))
 575          val = val_r;
 576  
 577        // if the decimal place is exactly 1/2 and the most LSB of mantiss is 1, then round-even the mantissa
 578        else if((check_r == 0x80000000) && (mantissa & 0x00000001))
 579          val = val_r;
 580        else
 581          val |= mantissa;
 582      }
 583  
 584    return val;
 585  
 586  }