Other ways to implement a circular shift?

Question

#include <stdio.h>
void char_to_bin(char c){
for(int i=0;i<8;i++){
if(c&0x80){ printf("%d",1);}
else {printf("%d",0);}
c=c<<1;
}
printf("\n");
}
int main() {
unsigned char a =0b11100111;
char_to_bin(a);
//Circular shifting
for(int j=0;j<32;j++){
if(a&0x80){
a<<=1;
a^=1;}
else{a<<=1;}
char_to_bin(a);
}
return 0;
}
https://code.sololearn.com/ch9jZG5qVA3I/?ref=app

Answer 1

david ortega I admit my code begs explanation. First, I started with your code:

if(a&0x80){
a<<=1;
a^=1;}
else{a<<=1;}

then I reduced it to this:
a = (a&0x80 != 0) | a<<1;

This uses the Boolean expression to translate the high bit (0x80 or 0) down to the low bit (1 or 0). Then by using bitwise Or on left-shifted a, it mimics bit rotation.

Now the final twist: On a signed char, the high bit is the sign bit. So if (a&0x80 != 0) is true, that means a is negative. So an equivalent test for the high bit is (a<0). Hence, it simplifies to:

a = (a<0) |a<<1;

I liked the syntax, though I had to change from unsigned to signed char. It is a faster test than above.

An unsigned char does not work because it never goes negative. You could use (a>=128) instead. My first reduction above would work on both types.

Answer 2

Here is a version that uses the CPUs "rotate left" instruction

#include <stdio.h>
void char_to_bin(char c){
for(int i=0;i<8;i++){
if(c&0x80){ printf("%d",1);}
else {printf("%d",0);}
c=c<<1;
}
printf("\n");
}

int main() {
unsigned char a =0b11100111;
char_to_bin(a);

//Circular shifting
for(int j=0;j<32;j++){
__asm (
"rolb $1, %0;"
: "=r" (a)
: "r" (a)
: "cc"
);
char_to_bin(a);
}

return 0;
}

Answer 3

I've made it into faster and smaller code, but it is doing it the same way:

#include <stdio.h>
void char_to_bin(char c) {
for(int i=8; i; i--, c<<=1)
putc('0'+(c<0), stdout);
putc('\n', stdout);
}
int main() {
char a = 0b11100111;
char_to_bin(a);
//Circular shifting
for(int j=0; j<32; j++) {
a = (a<0) | a<<1;
char_to_bin(a);
}
return 0;
}

Answer 4

Ani Jona 🕊 in principle, any code that comes afterward and depends on the carry flag should clear it first and not presume the carry flag is initialized to 0.

Answer 5

Ani Jona 🕊 You deserve an award 🏆for most authentic approach! I think the cc instruction is unnecessary.

It has long been a mystery to me why Kernighan omitted a bitwise rotate operator from C!

Answer 6

Thanks, Brian 😅

The documentation of ROL indicates that the flags register is affected, hence i added the cc.

Answer 7

From Brian:

#include <stdio.h>
void char_to_bin(char c) {
for(int i=8; i; i--, c<<=1)
putc('0'+(c<0), stdout);
putc('\n', stdout);
}
int main() {
char a = 0b11100111;
char_to_bin(a);
//Circular shifting
for(int j=0; j<32; j++) {
a = (a<0) | a<<1;
char_to_bin(a);
}
return 0;
}

I don't understand how "a=(a<0)|a<<1;" works. And why if I use "unsigned char a" instead of "char a" the code doesn't work?