3
\$\begingroup\$

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. The task is to convert the result of an arithmetic right shift to what would be the result of a logical right shift.

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%.8x\n", srl(-1, 1));
printf("srl(-1, 4): 0x%.8x\n", srl(-1, 4));
printf("srl(-1, 5): 0x%.8x\n", srl(-1, 5));
printf("srl(-1, 31): 0x%.8x\n", srl(-1, 31));
printf("srl(-1, 0): 0x%.8x\n", srl(-1, 0));

printf("srl(0x7FFFFFFF, 1): 0x%.8x\n", srl(0x7FFFFFFF, 1));
printf("srl(0x7FFFFFFF, 4): 0x%.8x\n", srl(0x7FFFFFFF, 4));
printf("srl(0x7FFFFFFF, 5): 0x%.8x\n", srl(0x7FFFFFFF, 5));
printf("srl(0x7FFFFFFF, 31): 0x%.8x\n", srl(0x7FFFFFFF, 31));
printf("srl(0x7FFFFFFF, 0): 0x%.8x\n", srl(0x7FFFFFFF, 0));

printf("srl(0x80000000, 1): 0x%.8x\n", srl(0x80000000, 1));
printf("srl(0x80000000, 4): 0x%.8x\n", srl(0x80000000, 4));
printf("srl(0x80000000, 5): 0x%.8x\n", srl(0x80000000, 5));
printf("srl(0x80000000, 31): 0x%.8x\n", srl(0x80000000, 31));
printf("srl(0x80000000, 0): 0x%.8x\n", srl(0x80000000, 0));

printf("srl(0, 1): 0x%.8x\n", srl(0, 1));
printf("srl(0, 4): 0x%.8x\n", srl(0, 4));
printf("srl(0, 5): 0x%.8x\n", srl(0, 5));
printf("srl(0, 31): 0x%.8x\n", srl(0, 31));
printf("srl(0, 0): 0x%.8x\n", srl(0, 0));

printf("srl(1, 1): 0x%.8x\n", srl(1, 1));
printf("srl(1, 4): 0x%.8x\n", srl(1, 4));
printf("srl(1, 5): 0x%.8x\n", srl(1, 5));
printf("srl(1, 31): 0x%.8x\n", srl(1, 31));
printf("srl(1, 0): 0x%.8x\n", 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     
\$\endgroup\$
  • \$\begingroup\$ @Reinderien Thanks for the edit. How do you get the closing brace "}" in the code section? It always drops out on me. \$\endgroup\$ – RJM Jan 21 at 4:15
  • 1
    \$\begingroup\$ Make sure that it's 4-tabbed in. \$\endgroup\$ – Reinderien Jan 21 at 4:16
  • \$\begingroup\$ Code is to do a "Logical Right Shift" yet is is called srl(). What does srl mean? Shift-Right-Logical? That 'l' is easier to see as implying left. \$\endgroup\$ – chux Jan 21 at 7:13
  • \$\begingroup\$ @chux that was what the problem called it. I could have changed it to make it clearer, but did not bother. \$\endgroup\$ – RJM Jan 21 at 13:14
  • \$\begingroup\$ @chux I did the change from logical to arithmetic last night with same requirements. The book called it sra. Real descriptive. \$\endgroup\$ – RJM Jan 21 at 13:19
3
\$\begingroup\$
  • Regarding all the implementation-defined behavior present:

    • In the general case, it is implementation-defined if right-shifting a negative number results in arithmetic shift or logical shift. It is up to the compiler to pick.
    • In your specific case, you go from unsignedx type to signed type (int)x. You have implicit, implementation-defined conversions from signed type to unsigned type and back. The program is allowed to raise a signal when going from a large unsigned int to int. So it is not a good idea, but no way around it as your program is written.
    • Meaning, at the point when we have executed the first line of your function, we have no idea of the state of the variable or the program as whole. On a specific system, it's another story, but your question is about generic C.
  • sizeof(int) << 3. Replacing multiplication by 8 with shifts manually is bad practice, known as "pre-mature optimization". Never do this, let the compiler handle it. Correct code should be 8 * sizeof(int) or CHAR_BIT * sizeof(int).

  • Regarding ~0 + !k. If k is 0, the result is -1 + 1 = 0, assuming two's complement. Otherwise, if k is not 0, the result is -1, which you then implicitly convert to unsigned type. What's the reason for writing such obfuscated code, are you trying to make the code more branch-friendly or something? Don't do that before you have found a bottleneck during benchmarking. Instead write:

    if(k==0)
    {
      zero_or_all_bits = 0;
    }
    else
    {
      zero_or_all_bits = ~0u;
    }
    

or if you prefer, unsigned int zero_or_all_bits = (k==0) ? 0u : ~0u.


As for how to convert the result of an arithmetic shift to a logical, without any questionable conversions or UB hiccups, simply do:

int val = x >> y;                // some manner of arithmetic shift
...
const size_t int_bits = sizeof(int) * 8;
unsigned int mask = (1u << y)-1; // create a mask corresponding to the number of shifts
mask = mask << (int_bits-y);     // shift the mask in place from MSB and down
mask = ~mask;                    // then invert the whole integer, making mask bits zero, rest ones
val = val & mask;                // set the bits to zero

That is, simply clear the bits which were set by arithmetic shift. This code was intentionally written in several steps to make it easier to understand.

For example, given x = -8 and y = 2:

  • x = -8 is 0xFFFFFFF8 hex (2's complement).
  • -8 >> 2 arithmetic shift gives 0xFFFFFFFE. Two zeroes getting shifted out, two ones shifted in.
  • The corresponding logical shift would be 0x3FFFFFFE. Two zeroes getting shifted out, two zeroes shifted in.
  • (1u << 2) gives 0x4. (1u << 2)-1 gives 0x3, a mask of ones 2 bits wide.
  • Shift the mask 0x3 in place, 32-2=30 bits to the left. Temporary value 0xC0000000.
  • Invert this, we get 0x3FFFFFFF which is the desired mask.
  • Data AND mask gives: 0xFFFFFFFE AND 0x3FFFFFFF = 0x3FFFFFFE.
\$\endgroup\$
  • \$\begingroup\$ @RJM Uh, sorry, that was posted in a hurry. Of course you'll want a generic case, not sure what I was thinking. I have updated the answer with a generic C code and an example, hope it is clearer. \$\endgroup\$ – Lundin Jan 22 at 16:08
  • \$\begingroup\$ @RJM As for UB, it doesn't apply unless we left shift a signed int with negative value, or in case we left shift data into the sign bit of a signed int. Which we avoid entirely by using unsigned int. \$\endgroup\$ – Lundin Jan 22 at 16:10
  • 1
    \$\begingroup\$ @RJM It's the type used that determines undefined behavior, not the raw binary representation. If you store 0xFFFFFFFF (-1) in an int and left shift, you get undefined behavior. If you store the same in an unsigned int and shift, it is well-defined. The C standard C17 6.5.7 is quite easy to read here: "The result of E1 << E2 is E1 left-shifted E2 bit positions" ... "If E1 has a signed type and non-negative value, and E1 × 2^E2 is representable in the result type, then that is the resulting value; otherwise, the behavior is undefined." \$\endgroup\$ – Lundin Jan 23 at 7:42
  • 1
    \$\begingroup\$ @RJM (1u << y)-1 evaluates the shift based on the type of the left operand. The result of the shift operators always have the type of the left operand (special case for shifts specifically). 1u has type unsigned int and so does the result. Then the result - 1 is evaluated. The rule called the usual arithmetic conversions ("type balancing") applies, the signed operand 1 is converted to unsigned, since the other operand is unsigned. More info: Implicit type promotion rules. \$\endgroup\$ – Lundin Jan 23 at 7:45
  • 1
    \$\begingroup\$ @RJM Also, mind the terms cast and conversion. A conversion is when an operand changes type, either implicitly or explicitly. A cast is when the programmer explicitly enforces a conversion with the cast () operator. \$\endgroup\$ – Lundin Jan 23 at 7:47
2
\$\begingroup\$

LGTM.

One recommendation is to split unsigned zero_or_all_bits = ~0 + !k; into two lines, like

    unsigned zero_or_all_bits = ~0;

    // 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

    zero_or_all_bits += !k;

Two other comments (// calculates and // creates mask) add no value. I recommend to remove them.

\$\endgroup\$
  • \$\begingroup\$ Thank you. I have never posted a question, so I figured I'd over comment. \$\endgroup\$ – RJM Jan 20 at 17:58
  • \$\begingroup\$ Good suggestion. The question said to write clear, understandable code. I found that difficult here. \$\endgroup\$ – RJM Jan 20 at 18:02
  • \$\begingroup\$ ~0 will not provide an all ones pattern to unsigned here on now rare non-2's complement machines. Best to use ~0u or -1u. \$\endgroup\$ – chux Jan 21 at 7:07
  • \$\begingroup\$ @chux Actually, I did not state it in my post, but the problem said to assume two's complement. \$\endgroup\$ – RJM Jan 21 at 13:20
  • \$\begingroup\$ @chux The ~ operator (as well as | & ^) doesn't care about the signedness format. ~ simply performs a bitwise complement of all bits. Not to be confused with 1's and 2's complement. It is however good practice to avoid signed integer constants when dealing with bitwise arithmetic, so 0u is good practice still. \$\endgroup\$ – Lundin Jan 23 at 7:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.