Velocity Reviews > Bit manipulation

# Bit manipulation

Carramba
Guest
Posts: n/a

 05-03-2007
Hi!

I have two integers and I want exchnge they bits from certain position
(Crossover) as follows:

int main()
unsigned int crossPos;
unsigned int b, b1;
unsigned int value1, value2;
unsigned int result1, result2;

b = value2<<(31-crossPos);
b = b >>(31-crossPos);
result1 = value1 | b;
b1 = value1<<(31-crossPos);
b1 = b1>>(31-crossPos);
result2 = value2 | b1;
return 0;
}

but code seems uggly and feels unsafe.. what way would you recommend for
exchanges bit from certain position and down?
[31a 30a ...5a 4a 3a 2a 1a 0a] and [31b 30b ...5b 4b 3b 2b 1b 0b] from
position 3 =>
result1 = [31a 30a ...5a 4a 3a 2b 1b 0b]
result2 = [31b 30b ...5b 4b 3b 2a 1a 0a]

Carra

Eric Sosman
Guest
Posts: n/a

 05-03-2007
Carramba wrote:
> Hi!
>
> I have two integers and I want exchnge they bits from certain position
> (Crossover) as follows:
> [...]
> but code seems uggly and feels unsafe.. what way would you recommend for
> exchanges bit from certain position and down?
> [31a 30a ...5a 4a 3a 2a 1a 0a] and [31b 30b ...5b 4b 3b 2b 1b 0b] from
> position 3 =>
> result1 = [31a 30a ...5a 4a 3a 2b 1b 0b]
> result2 = [31b 30b ...5b 4b 3b 2a 1a 0a]

/* assumes 32-bit int; could be generalized */
unsigned int olda = ...;
unsigned int oldb = ...;
int cross = ...; /* # of low-order bits to swap, 0..31 */
unsigned int highmask = -1u << cross;

--
Eric Sosman
http://www.velocityreviews.com/forums/(E-Mail Removed)lid

Hallvard B Furuseth
Guest
Posts: n/a

 05-03-2007
Carramba writes:
> but code seems uggly and feels unsafe.. what way would you recommend for
> exchanges bit from certain position and down?
> [31a 30a ...5a 4a 3a 2a 1a 0a] and [31b 30b ...5b 4b 3b 2b 1b 0b] from
> position 3 =>
> result1 = [31a 30a ...5a 4a 3a 2b 1b 0b]
> result2 = [31b 30b ...5b 4b 3b 2a 1a 0a]

/* n < (#bits in an unsigned int), otherwise behavior is undefined */
void crossover(unsigned *a, unsigned *b, unsigned n) {
unsigned mask = (1U << n) - 1;
unsigned swap = (*a ^ *b) & mask;
*a ^= swap;
*b ^= swap;
}

--
Hallvard

Richard Heathfield
Guest
Posts: n/a

 05-03-2007
Carramba said:

> Hi!
>
> I have two integers and I want exchnge they bits from certain position
> (Crossover) as follows:
>
> int main()
> unsigned int crossPos;
> unsigned int b, b1;
> unsigned int value1, value2;
> unsigned int result1, result2;
>
> b = value2<<(31-crossPos);
> b = b >>(31-crossPos);
> result1 = value1 | b;
> b1 = value1<<(31-crossPos);
> b1 = b1>>(31-crossPos);
> result2 = value2 | b1;
> return 0;
> }

I think you probably want something like this:

/* pre-condition:
* c MUST be fewer than the number of bits in an unsigned int;
* if it is not, the behaviour is undefined.
*/
unsigned int crossover(unsigned int x, unsigned int y, unsigned int c)
{
}

The following test driver should reveal flaws in the above function (or
indeed in the driver itself!) which will at least guide you to a
solution.

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

unsigned int crossover(unsigned int x, unsigned int y, unsigned int c)
{
}

void binstring(char *s, size_t len, unsigned int n)
{
if(len-- > 0)
{
memset(s, '0', len);
s[len] = '\0';
while(len-- > 0)
{
s[len] = '0' + (n & 1);
n >>= 1;
}
}
}

int main(void)
{
unsigned int cross = 0;
unsigned int m = 0x12345678UL;
unsigned int n = 0x9ABCDEF7UL;
char s[sizeof m * CHAR_BIT + 1] = "";
char t[sizeof n * CHAR_BIT + 1] = "";
binstring(s, sizeof s, m);
binstring(t, sizeof t, n);
for(cross = 0; cross < sizeof m * CHAR_BIT; cross++)
{
unsigned int r = crossover(m, n, cross);
binstring(s, sizeof s, r);
printf("Cross at %2u gives %08X %s\n", cross, r, s);
}
return 0;
}

--
Richard Heathfield
"Usenet is a strange place" - dmr 29/7/1999
http://www.cpax.org.uk
email: rjh at the above domain, - www.

Carramba
Guest
Posts: n/a

 05-03-2007
Thank you all! solutions were mutch more beutifull then mine!

have a nice day!

Peter Nilsson
Guest
Posts: n/a

 05-03-2007
Hallvard B Furuseth <(E-Mail Removed)> wrote:
> Carramba writes:
> > ... what way would you recommend for exchanges bit from
> > certain position and down?

>
> /* n < (#bits in an unsigned int), otherwise behavior is
> undefined */

It also works if a == b.

> void crossover(unsigned *a, unsigned *b, unsigned n) {
> unsigned mask = (1U << n) - 1;
> unsigned swap = (*a ^ *b) & mask;
> *a ^= swap;
> *b ^= swap;
> }

If there are N value bits in unsigned int, you can implement
n in (0..N] with...

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

If you want n in [0..N] then just test for n == 0...

mask = n ? (1u << n - 1 << 1) - 1 : 0;

--
Peter

Guest
Posts: n/a

 05-04-2007
Hallvard B Furuseth wrote:
> Carramba writes:
>
>>but code seems uggly and feels unsafe.. what way would you recommend for
>>exchanges bit from certain position and down?
>>[31a 30a ...5a 4a 3a 2a 1a 0a] and [31b 30b ...5b 4b 3b 2b 1b 0b] from
>>position 3 =>
>>result1 = [31a 30a ...5a 4a 3a 2b 1b 0b]
>>result2 = [31b 30b ...5b 4b 3b 2a 1a 0a]

>
>
> /* n < (#bits in an unsigned int), otherwise behavior is undefined */
> void crossover(unsigned *a, unsigned *b, unsigned n) {
> unsigned mask = (1U << n) - 1;
> unsigned swap = (*a ^ *b) & mask;
> *a ^= swap;
> *b ^= swap;
> }

This is an elegant implementation, but the mask is off by one position.
For example, if we want to exchange bits from position 1 and down, the
mask should be 3, not 1.

--

Hallvard B Furuseth
Guest
Posts: n/a

 05-05-2007
Peter Nilsson <(E-Mail Removed)> writes:
>Hallvard B Furuseth <(E-Mail Removed)> wrote:
>>Carramba writes:
>>> ... what way would you recommend for exchanges bit from
>>> certain position and down?

>>
>> /* n < (#bits in an unsigned int), otherwise behavior is
>> undefined */

>
> It also works if a == b.

When n >= #bits, you mean? No. It is behavior, not just the value,
which is undefined when n in x<<n is out of range. The program might
crash, for example.

--
Regards,
Hallvard

Hallvard B Furuseth
Guest
Posts: n/a

 05-05-2007
>Hallvard B Furuseth wrote:
>>Carramba writes:
>>>[31a 30a ...5a 4a 3a 2a 1a 0a] and [31b 30b ...5b 4b 3b 2b 1b 0b] from
>>>position 3 =>
>>>result1 = [31a 30a ...5a 4a 3a 2b 1b 0b]
>>>result2 = [31b 30b ...5b 4b 3b 2a 1a 0a]

>> /* n < (#bits in an unsigned int), otherwise behavior is undefined */
>> void crossover(unsigned *a, unsigned *b, unsigned n) {
>> unsigned mask = (1U << n) - 1;
>> unsigned swap = (*a ^ *b) & mask;
>> *a ^= swap;
>> *b ^= swap;
>> }

>
> This is an elegant implementation, but the mask is off by one
> position. For example, if we want to exchange bits from position 1 and
> down, the mask should be 3, not 1.

No, his example (quoted above) shows that for "position n", n bits
should be swapped.

--
Regards,
Hallvard

Guest
Posts: n/a

 05-06-2007
Hallvard B Furuseth wrote:
>
>>Hallvard B Furuseth wrote:
>>
>>>Carramba writes:
>>>
>>>>but code seems uggly and feels unsafe.. what way would you recommend for
>>>>exchanges bit from certain position and down?
>>>>[31a 30a ...5a 4a 3a 2a 1a 0a] and [31b 30b ...5b 4b 3b 2b 1b 0b] from
>>>>position 3 =>
>>>>result1 = [31a 30a ...5a 4a 3a 2b 1b 0b]
>>>>result2 = [31b 30b ...5b 4b 3b 2a 1a 0a]
>>>
>>>/* n < (#bits in an unsigned int), otherwise behavior is undefined */
>>>void crossover(unsigned *a, unsigned *b, unsigned n) {
>>> unsigned mask = (1U << n) - 1;
>>> unsigned swap = (*a ^ *b) & mask;
>>> *a ^= swap;
>>> *b ^= swap;
>>>}

>>
>>This is an elegant implementation, but the mask is off by one
>>position. For example, if we want to exchange bits from position 1 and
>>down, the mask should be 3, not 1.

>
> No, his example (quoted above) shows that for "position n", n bits
> should be swapped.

Ah, the old "which is correct, the example or the specification"
problem. I looked at the wording and didn't see the discrepancy with
the example.

--

 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 OffTrackbacks are On Pingbacks are On Refbacks are Off Forum Rules

 Similar Threads Thread Thread Starter Forum Replies Last Post Scotius Digital Photography 6 07-13-2010 03:33 AM benn686@hotmail.com C++ 9 08-22-2007 12:13 AM markryde@gmail.com Java 3 01-19-2007 10:30 PM vvcd Computer Support 0 09-17-2004 08:15 PM Ionizer Computer Support 1 01-01-2004 07:27 PM