# Bit manipulation

Discussion in 'C Programming' started by Carramba, May 3, 2007.

1. ### CarrambaGuest

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]

Thanx in advance

Carra

Carramba, May 3, 2007

2. ### Eric SosmanGuest

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;
unsigned int newa = (olda & highmask) | (oldb & ~highmask);
unsigned int newb = (oldb & highmask) | (olda & ~highmask);

--
Eric Sosman
lid

Eric Sosman, May 3, 2007

3. ### Hallvard B FurusethGuest

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

Hallvard B Furuseth, May 3, 2007
4. ### Richard HeathfieldGuest

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)
{
unsigned int maska = -1U;
unsigned int maskb = 0;
maska >>= c;
maskb = ~maska;
return (x & maskb) | (y & maska);
}

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)
{
unsigned int maska = -1U;
unsigned int maskb = 0;
maska >>= c;
maskb = ~maska;
return (x & maskb) | (y & maska);
}

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] = "";
char pad[] = " ";
binstring(s, sizeof s, m);
binstring(t, sizeof t, n);
printf("Inputs:\n%s%08X %s\n%s%08X %s\n", pad, m, s, pad, n, t);
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.

Richard Heathfield, May 3, 2007
5. ### CarrambaGuest

Thank you all! solutions were mutch more beutifull then mine!

have a nice day!

Carramba, May 3, 2007
6. ### Peter NilssonGuest

Hallvard B Furuseth <> 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

Peter Nilsson, May 3, 2007
7. ### Thad SmithGuest

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.

--
Thad

Thad Smith, May 4, 2007
8. ### Hallvard B FurusethGuest

Peter Nilsson <> writes:
>Hallvard B Furuseth <> 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, May 5, 2007
9. ### Hallvard B FurusethGuest

Thad Smith writes:
>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

Hallvard B Furuseth, May 5, 2007
10. ### Thad SmithGuest

Hallvard B Furuseth wrote:
> Thad Smith writes:
>
>>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.

--
Thad

Thad Smith, May 6, 2007
11. ### Peter NilssonGuest

Hallvard B Furuseth <> wrote:
> Peter Nilsson <> writes:
> > Hallvard B Furuseth <> wrote:
> > > /* n < (#bits in an unsigned int), otherwise behavior
> > > is undefined */

> >
> > It also works if a == b.

>
> When n >= #bits, you mean?

No. I mean that your function works if a and b point to the
same object. In contrast, consider...

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

If a == b, then this will simply zero the lower n bits.

--
Peter

Peter Nilsson, May 6, 2007

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

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.