Gfrktyl

The following code is a solution to a textbook (Bryant&O'Hallaron: Computer Systems A programmer's Perspective 2nd Ed) problem in bit-level data manipulation (attempted for the challenge, not a class). The function srl is not written necessarily in a practical manner, but within the constraints required by the problem.

Questions

Is there is a clearer, more straight-forward way to write this within the required constraints of the problem (perhaps with fewer ~ operations)?

There is a need to avoid undefined behavior of the left shift, when k = 0. In this case int_bits - k = int_bits, which causes the shift to work unpredictably. Is there a better way to handle the undefined behavior of the shift operations, when the shift is larger than the number of bits in the interger?

It seems to work correctly, but I lack an answer, so any feedback on the solution would be appreciated.

Requirements

• 
  

  No additional right shifts or type casts may be used beyond the given expression

  
  
  

    /*Perform shift arithmetically*/
  
     unsigned xsra = (int) x >> k;
  
  

  
  



• Only addition or subtraction may be used, no multiplication, division, or modulus




• No comparison operators and no conditionals




• Only bit-wise operations (except further right shifts) and logical operators may be used

Code

unsigned srl(unsigned x, int k) {

    /*Perform shift arithmetically*/

    unsigned xsra = (int) x >> k;



    unsigned int_bits = sizeof(int) << 3;//calculates the number of bits in int (assumes 8-bit byte)



    unsigned zero_or_all_bits = ~0 + !k;//for k = 0, corrects for the undefined behavior in

                                        //the left shift produced from int_bits - k = int_bits

                                        //if k != 0, !k == 0, and zero_or_all_bits == ~0

                                        //if k == 0, zero_or_all_bits == 0



    unsigned high_bit_mask = ~(zero_or_all_bits << (zero_or_all_bits & (int_bits - k)));

    /******************************************/

    //creates a mask of either all bits set in an unsigned int (UINT_MAX)

    //or a mask with k high bits cleared.

    //if k == 0, then high_bit_mask = ~(0 << 0) = ~0.

    //if k != 0, then high_bit_mask = ~(~0 << (~0 & (int_bits - k)))

    //ex. k == 3, high_bit_mask == 0x1FFFFFFF

    //ex. k == 0, high_bit_mask == 0xFFFFFFFF

    //ex. k == 31, high_bit_mask == 0xFFFFFFFE

    /******************************************/



    return xsra & high_bit_mask;

}

Test Code

printf("Test srl:n");

printf("srl(-1, 1): 0x%.8xn", srl(-1, 1));

printf("srl(-1, 4): 0x%.8xn", srl(-1, 4));

printf("srl(-1, 5): 0x%.8xn", srl(-1, 5));

printf("srl(-1, 31): 0x%.8xn", srl(-1, 31));

printf("srl(-1, 0): 0x%.8xn", srl(-1, 0));



printf("srl(0x7FFFFFFF, 1): 0x%.8xn", srl(0x7FFFFFFF, 1));

printf("srl(0x7FFFFFFF, 4): 0x%.8xn", srl(0x7FFFFFFF, 4));

printf("srl(0x7FFFFFFF, 5): 0x%.8xn", srl(0x7FFFFFFF, 5));

printf("srl(0x7FFFFFFF, 31): 0x%.8xn", srl(0x7FFFFFFF, 31));

printf("srl(0x7FFFFFFF, 0): 0x%.8xn", srl(0x7FFFFFFF, 0));



printf("srl(0x80000000, 1): 0x%.8xn", srl(0x80000000, 1));

printf("srl(0x80000000, 4): 0x%.8xn", srl(0x80000000, 4));

printf("srl(0x80000000, 5): 0x%.8xn", srl(0x80000000, 5));

printf("srl(0x80000000, 31): 0x%.8xn", srl(0x80000000, 31));

printf("srl(0x80000000, 0): 0x%.8xn", srl(0x80000000, 0));



printf("srl(0, 1): 0x%.8xn", srl(0, 1));

printf("srl(0, 4): 0x%.8xn", srl(0, 4));

printf("srl(0, 5): 0x%.8xn", srl(0, 5));

printf("srl(0, 31): 0x%.8xn", srl(0, 31));

printf("srl(0, 0): 0x%.8xn", srl(0, 0));



printf("srl(1, 1): 0x%.8xn", srl(1, 1));

printf("srl(1, 4): 0x%.8xn", srl(1, 4));

printf("srl(1, 5): 0x%.8xn", srl(1, 5));

printf("srl(1, 31): 0x%.8xn", srl(1, 31));

printf("srl(1, 0): 0x%.8xn", srl(1, 0));

Output

Test srl:

srl(-1, 1): 0x7fffffff

srl(-1, 4): 0x0fffffff

srl(-1, 5): 0x07ffffff

srl(-1, 31): 0x00000001

srl(-1, 0): 0xffffffff

srl(0x7FFFFFFF, 1): 0x3fffffff

srl(0x7FFFFFFF, 4): 0x07ffffff

srl(0x7FFFFFFF, 5): 0x03ffffff

srl(0x7FFFFFFF, 31): 0x00000000

srl(0x7FFFFFFF, 0): 0x7fffffff

srl(0x80000000, 1): 0x40000000

srl(0x80000000, 4): 0x08000000

srl(0x80000000, 5): 0x04000000

srl(0x80000000, 31): 0x00000001

srl(0x80000000, 0): 0x80000000

srl(0, 1): 0x00000000

srl(0, 4): 0x00000000

srl(0, 5): 0x00000000

srl(0, 31): 0x00000000

srl(0, 0): 0x00000000

srl(1, 1): 0x00000000

srl(1, 4): 0x00000000

srl(1, 5): 0x00000000

srl(1, 31): 0x00000000

srl(1, 0): 0x00000001