Bit manipulation

[Carramba]

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

 

[Eric Sosman]

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);

 

[Hallvard B Furuseth]

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;
}

 

[Richard Heathfield]

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;
}

 

[Carramba]

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

have a nice day!

 

[Peter Nilsson]

/* 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;

 

[Thad Smith]

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]

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.

 

[Hallvard B Furuseth]

[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.

 

[Thad Smith]

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.

 

[Peter Nilsson]

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.