Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > C Programming > Shifting bits

Reply
Thread Tools

Shifting bits

 
 
jacob navia
Guest
Posts: n/a
 
      10-27-2009
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[i]&1;
p[i] = (p[i] >> 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
 
Reply With Quote
 
 
 
 
Alan Curry
Guest
Posts: n/a
 
      10-27-2009
In article <hc7o05$eil$(E-Mail Removed)>, jacob navia <(E-Mail Removed)> wrote:
>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[i]&1;
> p[i] = (p[i] >> 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[i] & 1;
p[i] = (p[i]>>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.

--
Alan Curry
 
Reply With Quote
 
 
 
 
jacob navia
Guest
Posts: n/a
 
      10-27-2009
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[i] & 1;
> p[i] = (p[i]>>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.
 
Reply With Quote
 
Morris Keesan
Guest
Posts: n/a
 
      10-28-2009
On Tue, 27 Oct 2009 17:17:05 -0400, jacob navia <(E-Mail Removed)> wrote:

> 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").

--
Morris Keesan -- http://www.velocityreviews.com/forums/(E-Mail Removed)
 
Reply With Quote
 
Peter Nilsson
Guest
Posts: n/a
 
      10-28-2009
jacob navia <(E-Mail Removed)> wrote:
> 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[i]&1;
> * * * * * * * * *p[i] = (p[i] >> 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;
}

--
Peter
 
Reply With Quote
 
jacob navia
Guest
Posts: n/a
 
      10-28-2009
Morris Keesan a écrit :
> On Tue, 27 Oct 2009 17:17:05 -0400, jacob navia <(E-Mail Removed)> wrote:
>
>> 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.
>

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.
 
Reply With Quote
 
jacob navia
Guest
Posts: n/a
 
      10-28-2009
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;
> }
>
> --
> Peter


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
 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
Shifting bits arnuld C Programming 31 12-01-2011 09:34 PM
Shifting unsigned long long values by 64 bits krunalb C Programming 10 01-23-2007 02:47 PM
shifting bits, shift 32 bits on 32 bit int GGG C++ 10 07-06-2006 06:09 AM
8-Bits vs 12 or 16 bits/pixel; When does more than 8 bits count ? Al Dykes Digital Photography 3 12-29-2003 07:08 PM
win XP 32 bits on a 64 bits processor.. Abbyss Computer Support 3 11-13-2003 12:39 AM



Advertisments