Print Bits Part III

Question

The last question I have been playing around with is a right rotate. I think it is also called a barrel roll. Please post if you have a better solution please post. I am still learning the art of bit flipping.

/*
 * Next write a function rightrot(x,n) that returns the value of the
 * integer x rotated to the right by n bit positions
 *
 * build with:
 *   gcc -o bit_twiddle -Wall -g -lm ./bit_twiddle.c
 */

#include <stdio.h>
#include <math.h>
#include <limits.h>

size_t size_of_int = sizeof(int) << 3;

void printbits(unsigned x) {
    unsigned mask = 1 << (size_of_int - 1);
    int i = 0;
    for(i = 1; i <= size_of_int; ++i, x <<= 1) {
       ((x & mask) == 0) ? printf("0") : printf("1");
       (((i % 4))==0) ? printf(" ") : printf("%s","");
    }
    printf("\n");
}

void rightrot(unsigned x, unsigned n) {
    printf("%15s =", "rightrot"); printbits((((~(~0 << n)) & x) << (size_of_int - n)) | (x >> n));
}

int main(int argc, char *argv[]) {
    unsigned input=4042322167, nbits=4;
    printf("%15s =", "x"); printbits(input);
    rightrot(input, nbits);
    return(0);
}

Answer 1

What is this supposed to be?

size_t size_of_int = sizeof(int) << 3;

The shift left by 3 is very cryptic. Multiply by 8 or explain what you are doing. But a better solution is to multiply the number of bytes by the actual bits in a byte.

If you want the number of bits in an integer:

#include <climits>
size_t size_of_int = sizeof(int) * CHAR_BIT;;

PrintBits()

People are more used to seeing loops from 0:

for(i = 1; i <= size_of_int; ++i, x <<= 1)

// So prefer to loop from zero 

for(i = 0; i < size_of_int; ++i, x <<= 1)

This is an ugly way of printing 0/1

((x & mask) == 0) ? printf("0") : printf("1");

Only do one print: Then use the expression to decide what to print:
The expression (x & mask) == 0 is overkill if is zero then it is already false.

printf("%d", (x & mask) ? 1 : 0);

Again an ugly way to print a space every four places:

(((i % 4))==0) ? printf(" ") : printf("%s","");

// Personally I would just use an if

if (i%4==0) { printf(" ");}

• Is the result really a void? What happens if any of the printf() statements you use fail. In reality you should be checking the return codes of any function you call and either handling the error or passing the error back to the caller for them to handle.
• Your print function is very limited and only prints to the stdout. You should really make a version that prints to a stream

The function declarations should be:

int printbits(unsigned x) {return fprintbits(stdout, x);}
int fprintbits(FILE*, unsigned x)
{
    // Code Here
}

RightRot()

Why are you callint printbits() from rightrot()? The function should do one task and that is rotate the bits. If you want to print the result fine. But this function should not be doing the printing.

• So you need to change your signature so it can return the result

Refactoring

unsigned rightrot(unsigned x, unsigned n)

• Doing everything on one line. Just makes the code unreadable. Split it up. One statement per line. Nobody will give you extra marks for writing compressed code (but they will give you marks for writing clear code)

Refactoring:

 return ((((~(~0 << n)) & x) << (size_of_int - n)) | (x >> n));

Even after removing all the chaff the above line is still unreadable. Split it up into multiple statements and use temporaries. This way you can comment on what is happening. Its not as if a single line is more efficient. The compiler is going to remove any unused temporaries.

 // Shift right. Note: We loose bottom n bits (these need to be recovered.
 unsigned  base = x >> n;

 // Create a mask for the bottom n bits.
 unsigned  mask = (~(~0 << n));

 // Move the bottom n bits to the top of integer (as if they had wrapped around:
 unsigned  wrap = (x & mask) << (size_of_int - n);

 return wrap | base;

Now that we can read what is happening. We see that creating the mask can be done more clearly.

 unsigned  mask  = (1 << n) - 1;

We can also see that the calculation of wrap is overkill. All variables are unsigned and bits that fall of the top are lost.

 unsigned  wrap = x << (size_of_int - n);

Also note: That if n >= size_of_int you are going to be left with zero. So the first thing you should do is make sure that n is in the correct range. Let us assume a value greater will just wrap around multiple times.

// Multiple wraps do not add anything.
n = n %  size_of_int; 

Usage (from main)

fprintbits(stdout, rightrot(input, nbits));