I don't really know why bit-shifting works in one scenario but not the other

Question

So I am doing some bit-shifting and i have come to the following problem, that i would be more than grateful to get an answer to:

As an argument I'm allowed to pass the size of 1 byte.

The first 4 bits represent a numerator. The last 4 bits represent the denominator.

The following code works and gives the correct output:

#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>

int main(int argc, char** argv)
{
    for(int i = 1; i < argc; i++)
    {
        unsigned char numerator = atoi(argv[i]);
        numerator = (numerator >> 4);
        numerator = (numerator << 4);

        unsigned char denominator = atoi(argv[i]);
        denominator = (denominator << 4);
        denominator = (denominator >> 4);
        printf("%d/%d\n", numerator, denominator);
    }

    return 0;
}

But if i substitute the bit shifting part like this, the denominator gives the same output as the numerator:

unsigned char numerator = atoi(argv[i]);
        numerator = (numerator >> 4) << 4;

unsigned char denominator = atoi(argv[i]);
        denominator = (denominator << 4) >> 4;

sample input would be:

./test 1
./test 16

output given:

0/1
16/16

expected output:

0/1
16/0

Thanks in advance for any sort of help.

Please edit your question to include some sample "input", and the expected as well as the actual output for the failing case. — Some programmer dude, Apr 25 '20 at 23:11
I also recommend that you take a look at the generated code to see what (possibly optimized) machine code the compiler generates for your expressions. — Some programmer dude, Apr 25 '20 at 23:11
One difference is that in the second one, the intermediate value remains as `int` because of type promotions. So the upper 4 bits won't get removed in the left-then-right shifts. But in the right-then-left shifts there is nowhere for the ls. 4 bits to be held. — Weather Vane, Apr 25 '20 at 23:11
On a couple of unrelated notes: Why do you call `atoi` twice, instead of saving the value in a variable? And why don't you use bit-masking instead of shifting? — Some programmer dude, Apr 25 '20 at 23:14
is it faster if i call atoi into a variable and pass that variable than if i call atoi twice? — Sh1r, Apr 25 '20 at 23:16
@Sh1r that is one read and one write vs. a function processing a string. — Weather Vane, Apr 25 '20 at 23:17
I would have expected the numerator to simply be `value >> 4` not `((value >> 4) << 4`). Isn't that the whole point of the value doing double duty, holding both the numerator (shifted left 4) plus the denominator? You should use `((value & 0xF0) >> 4)` for the numerator and `value & 0x0F` for the denominator. — jarmod, Apr 25 '20 at 23:21
@Sh1r of course calling `atoi` only once must be faster. It such a tiny program it may not make much of a difference but for bigger programs it may increase run time a lot. And why don't you just AND the value with a mask if you want to clear bits? `denominator & 0x0F` would be far simpler and readable. And use hexadecimal inputs if you want to deal with bitwise operators. Inputting decimal numbers to the program doesn't make sense — phuclv, Apr 26 '20 at 01:51

score 5 · Accepted Answer · answered Apr 26 '20 at 00:33

When arithmetic expressions are evaluated in C, any integral types smaller than int are promoted to int before the calculations are performed.

So this code:

unsigned char denominator = atoi(argv[i]);
denominator = (denominator << 4);
denominator = (denominator >> 4);

results in the following sequence (each box represents 4 bits, and the text in the box is a hex digit):

Note that the assignment denominator = (denominator << 4); forces the compiler to convert the value back to an unsigned char. Then on the next line of code, the compiler needs to promote the unsigned char back to an int.

But this code:

unsigned char denominator = atoi(argv[i]);
denominator = (denominator << 4) >> 4;

skips the conversion back to unsigned char and the second promotion to int. So the sequence is:

Note that the final value is the same as the original value, since the shifting was performed using 32-bits, and nothing was shifted off the left side of the 32-bit value.

The numerator doesn't have the same problem. Because the numerator is shifted right first, the bits on the right are lost. The promotion to int has no effect on the results. Here's the sequence for the numerator:

score 3 · Answer 2 · answered Apr 25 '20 at 23:31

3

It seems that the values are being cast to a larger integer type (such as int), and when the shifts are performed, the upper bits are being preserved in the larger int type, then the result is cast back to unsigned char after both shifts are complete.

I would use a bitmask like this, instead of shifting:

...
unsigned char data = atoi(argv[i]);
unsigned char numerator = data & 0xf0;
unsigned char denominator = data & 0xf;
...

answered Apr 25 '20 at 23:31

Willis Hershey

1,520
4
22

1

There is no cast here. – chux - Reinstate Monica Apr 26 '20 at 01:04
1

There is an implicit conversion, as there always is with smaller-than-int types. – Chris Dodd Apr 26 '20 at 02:01

score 1 · Answer 3 · answered Apr 25 '20 at 23:44

The problem case is the denominator, for which the size of the variable is a factor. In the first version, you have:

    denominator = (denominator << 4);
    denominator = (denominator >> 4);

This shifts the value left by 4, then truncates it to fit into an unsigned char, then right shifts the result. In the case of 16, the first shift produces 256, which is then truncated to 0 when stored in denominator. The right shift then merely shifts 0.

In the second version, you have:

    denominator = (denominator << 4) >> 4;

This left shifts it by 4, without truncating the result to fit into an unsigned char, then right shifts the un-truncated result. In the case of 16, the first shift shift produces 256, which is then right-shifted back to 16.

To get a one-line equivalent of the first version, you could do:

    denominator = (unsigned char)(denominator << 4) >> 4;

I don't really know why bit-shifting works in one scenario but not the other

3 Answers3

Linked