Shifting bits

J

jacob navia

Given a bitstring of size siz (in bytes), shift it right by 1 bit.
Return the bit that was shifted out

static int Shift(char *p,size_t siz)
{
int carry;
size_t i;

carry = p[0]&1;
p[0] >>= 1;
for (i=1; i<siz;i++) {
int s = p&1;
p = (p >> 1) | (carry << 7);
if (i < siz-1)
carry = p[i+1]&1;
else carry = s;
}
return carry;
}

Somehow it doesn't look very well. I am sure that there is a better solution.

Any takers?

jacob
 
A

Alan Curry

Given a bitstring of size siz (in bytes), shift it right by 1 bit.
Return the bit that was shifted out

static int Shift(char *p,size_t siz)
{
int carry;
size_t i;

carry = p[0]&1;
p[0] >>= 1;
for (i=1; i<siz;i++) {
int s = p&1;
p = (p >> 1) | (carry << 7);
if (i < siz-1)
carry = p[i+1]&1;
else carry = s;
}
return carry;
}

Somehow it doesn't look very well. I am sure that there is a better solution.


Have you tested it? If that produces the result you wanted I'd like to see
your test case. It failed mine.

Here's the test case I used, together with my working implementation. The key
idea is to set the "carry" variable to be the value that will be shifted into
the top bit of the next byte. Set that to 0 before the loop starts, and you
don't have to special-case the first byte.

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

static int Shift(char *p,size_t siz)
{
size_t i;
int carry;

carry = 0;
for(i=0 ; i<siz ; ++i) {
int s = p & 1;
p = (p>>1) | (carry<<(CHAR_BIT-1));
carry = s;
}
return carry;
}

int main(void)
{
char testdat[8] = "\xfe\xed\xfa\xce\xde\xad\xbe\xef";
size_t i;
int bit;

for(i=0 ; i < sizeof(testdat)*CHAR_BIT ; ++i) {
bit = Shift(testdat, sizeof(testdat));
printf("Got bit %d\n", bit);
}

return 0;
}

Verified with

cc shiftbits.c -o shiftbits && ./shiftbits |
tr -cd 01 | perl -nle 'print unpack "H*", pack "B*", scalar reverse $_'

It's pretty easy to eliminate the variable 'i' from the shift function too.
Write the loop like this:

while(siz) {
int s = *p & 1;
*p = (*p>>1) | (carry<<(CHAR_BIT-1));
carry = s;
--siz;
++p;
}

Decide for yourself whether that's an improvement or not.
 
J

jacob navia

Alan Curry a écrit :
Here's the test case I used, together with my working implementation. The key
idea is to set the "carry" variable to be the value that will be shifted into
the top bit of the next byte. Set that to 0 before the loop starts, and you
don't have to special-case the first byte.

Right. That is the idea I as missing. Thanks a lot.
#include <stdio.h>
#include <limits.h>

static int Shift(char *p,size_t siz)
{
size_t i;
int carry;

carry = 0;
for(i=0 ; i<siz ; ++i) {
int s = p & 1;
p = (p>>1) | (carry<<(CHAR_BIT-1));
carry = s;
}
return carry;
}


It looks cleaner of course.
It's pretty easy to eliminate the variable 'i' from the shift function too.
Write the loop like this:

while(siz) {
int s = *p & 1;
*p = (*p>>1) | (carry<<(CHAR_BIT-1));
carry = s;
--siz;
++p;
}

Decide for yourself whether that's an improvement or not.

It is an improvement in the sense it looks clearer.

Thanks again.
 
M

Morris Keesan

Given a bitstring of size siz (in bytes), shift it right by 1 bit.
Return the bit that was shifted out

static int Shift(char *p,size_t siz)

static int Shift(unsigned char *p, size_t size)


1) If p is a (char *p), you'll get incorrect results on any platform
where "plain char" is signed.

2) "size" is not a reserved word. Why not call the variable what it
is? (cf. Dennis Ritchie supposedly saying that his only regret in
the original design of Unix was using the name "creat" instead of
"create").
 
P

Peter Nilsson

jacob navia said:
Given a bitstring of size siz (in bytes), shift it
right by 1 bit. Return the bit that was shifted out

static int Shift(char *p,size_t siz)
{
         int carry;
        size_t i;

         carry = p[0]&1;
         p[0] >>= 1;
         for (i=1; i<siz;i++) {
                 int s = p&1;
                 p = (p >> 1) | (carry << 7);
                 if (i < siz-1)
                         carry = p[i+1]&1;
                 else carry = s;
         }
         return carry;

}


If you're prepared to limit the code to implementations
where UINT_MAX > UCHAR_MAX, then just use a shift register...

#include <limits.h>
#include <stddef.h>

int asr(unsigned char *p, size_t z)
{
unsigned b;

for (b = 0; z--; p++)
{
b = (b << CHAR_BIT) | *p;
*p = b >> 1;
}

return b & 1;
}
 
J

jacob navia

Morris Keesan a écrit :
static int Shift(unsigned char *p, size_t size)


1) If p is a (char *p), you'll get incorrect results on any platform
where "plain char" is signed.
OK. Will change that. Thanks
2) "size" is not a reserved word. Why not call the variable what it
is? (cf. Dennis Ritchie supposedly saying that his only regret in
the original design of Unix was using the name "creat" instead of
"create").

"siz" is an abbreviation I always use for size for "hysterical reasons"...

I never thought about it since I am so used to it that I do not even
realize it is an abbreviation.
 
J

jacob navia

Peter Nilsson a écrit :
If you're prepared to limit the code to implementations
where UINT_MAX > UCHAR_MAX, then just use a shift register...

#include <limits.h>
#include <stddef.h>

int asr(unsigned char *p, size_t z)
{
unsigned b;

for (b = 0; z--; p++)
{
b = (b << CHAR_BIT) | *p;
*p = b >> 1;
}

return b & 1;
}

Well, that is a very good solution!

Now that I see this I remember I use this solution in the assembly code
for the extended precision floats that I have in lcc-win. I am getting
old, or maybe I am just tired. Thanks a lot for your excellent solution.

jacob
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

No members online now.

Forum statistics

Threads
473,744
Messages
2,569,484
Members
44,903
Latest member
orderPeak8CBDGummies

Latest Threads

Top