reflecting bit field

J

Jeremy Targett

Hello, I've been using a routine that reflects the bits in a field of
length 12, keeping the lowest one in place. So this ordering of bits:

12 11 10 9 8 7 6 5 4 3 2 1

gets mapped into this ordering:

2 3 4 5 6 7 8 9 10 11 12 1

What I'd like to do instead is to get the circular rotation of the
reflection that exchanges the position of the highest and lowest bits
that happen to be set. For example,

000100110011 ==> 000110011001

Could anyone suggest how to modify my code so it accomplishes this? Many
thanks --Jeremy

#define MASK 07777
#define OVER 010000

reflect(unsigned x)
{
unsigned t;
int i;
t = 0;

for (i = 0; i < 12; i++)
{
t |= (x & 001);
x >>= 1;
t = rotate(t);
}

return t;
}

rotate(unsigned x)
{
x <<= 1;
if (x & OVER)
x |= 001;
return(x & MASK);
}
 
T

Thad Smith

Jeremy said:
What I'd like to do instead is to get the circular rotation of the
reflection that exchanges the position of the highest and lowest bits
that happen to be set. For example,

000100110011 ==> 000110011001

Could anyone suggest how to modify my code so it accomplishes this? Many
thanks --Jeremy

#define MASK 07777
#define OVER 010000

reflect(unsigned x)
{
unsigned t;
int i;
t = 0;

for (i = 0; i < 12; i++)
{
t |= (x & 001);
x >>= 1;
t = rotate(t);
}

return t;
}

Stop your reflection loop when x becomes 0. If you do this, you can use
a plain left shift instead of a left rotate.

Thad
 
A

Alex Fraser

[snip]
What I'd like to do instead is to get the circular rotation of the
reflection that exchanges the position of the highest and lowest bits
that happen to be set. For example,

000100110011 ==> 000110011001

In other words, reverse the order of the bits from the most significant set
bit to the least significant set bit, inclusive?

eg 10110000 -> 11010000

Untested code:

unsigned reflect(unsigned x) {
unsigned m;
unsigned r;

if (x == 0) return 0;
m = x & -x; /* like: for (m = 1; !(x & m); m <<= 1); (x non-zero) */
r = 0;
do {
r = (r << 1) | (x & m); /* shift r left, copy a bit */
x = (x & ~m) >> 1; /* clear copied bit, shift x right */
} while (x);

return r;
}

Alex
 
J

jeremy targett

Thad Smith said:
Jeremy Targett wrote:
Stop your reflection loop when x becomes 0. If you do this, you can use
a plain left shift instead of a left rotate.

Thanks Thad, that worked out great. Here's how it ended up, for future
reference:

reflect(unsigned x)
{
unsigned t;
int i;
t = 0;

while (x!=0)
{
t |= (x & 001);
x >>= 1;
t <<= 1;
}
t >>= 1;
return t;
}

It wasn't clear to me why I needed the extra right-shift at the end, but
that's what works. Best -Jeremy
 
A

Alex Fraser

jeremy targett said:
[snip]
Thanks Thad, that worked out great. Here's how it ended up, for future
reference:

reflect(unsigned x)
{
unsigned t;
int i;
t = 0;

while (x!=0)
{
t |= (x & 001);
x >>= 1;
t <<= 1;
}
t >>= 1;
return t;
}

It wasn't clear to me why I needed the extra right-shift at the end, but
that's what works. Best -Jeremy

The left shift makes space for the next bit from x. On the last iteration,
there isn't a next bit, so you must remove the space you just created after
the loop ends. (It doesn't seem to be a problem in your case but this gives
an incorrect result if the MSB and LSB of x are set, eg reflect(0x80000001)
with 32-bit unsigned int.)

You can move the left shift to the top of the loop (and remove the extra
shift):

unsigned reflect(unsigned x) {
unsigned t = 0;
while (x) {
t <<= 1;
t |= x & 1;
x >>= 1;
}
return t;
}

Alex
 

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