sgoldburg - 6 months ago 135

C Question

This question is similar in nature to: Is -!(condition) a correct way to obtain a full-bitvector from a boolean (mask-boolean)?

As part of a HW solution, I would like to implement a conditional check and subsequent assignment of all "1" or "0" bits to a 32bit int.

My code is :

`value & ~(!(x & y) - 1)`

My question is how to optimize this statement to reduce the number of operators involved. Is this possible using only unary and binary integer operations

`! ~ & ^ | + - * / % << >>`

Here is my code for some reference, it repeats the low-order n bits of x to word length:

`int bitRepeat(int x, int n) {`

/* Mask desired bits, shift and OR by larger intervals each time, return repeated pattern */

/* Check for n = 32, set a to all 1's if n != 32 */

int nMax = ~(!(n & 31)-1);

/* Mask low-order n bits */

int maskBits = ~(~0 << n) & x;

/* Initialize shift factors */

int n2 = n * 2;

int n4 = n * 4;

int n8 = n * 8;

int n16 = n * 16;

/* Shift and OR masked bits by intervals n * x {x: 1,2,4,8,16}, check for overflow at each step */

int overFlowMask = ~0 << 5;

maskBits = maskBits | maskBits << n;

maskBits = maskBits | ((maskBits << (n2)) & ~(!((n2) & overFlowMask) - 1));

maskBits = maskBits | ((maskBits << (n4)) & ~(!((n4) & overFlowMask) - 1));

maskBits = maskBits | ((maskBits << (n8)) & ~(!((n8) & overFlowMask) - 1));

maskBits = maskBits | ((maskBits << (n16)) & ~(!((n16) & overFlowMask) - 1));

return (maskBits & ~nMax) | (x & nMax);

}

Would implementing

`unsigned`

Answer

You can do it a lot easier (we want to fill an integer with n repeats of a bit pattern).

```
unsigned int bitRepeat(unsigned int x, int n)
{
unsigned int answer = 0;
while(x)
{
answer |= x;
x <<= n;
}
return answer;
}
```

You need to use unsigned integers because shifting out the MSB of a signed integer can have unpredictable consequences. (Because the compiler might optimise to x *= poweroftwo, and have arithmetical overflow traps set).

Since you can't use loops, it becomes a bit more difficult. As you observed, if integers are 32 bits, then worst case is we double the buffer five times.

so

```
int bitRepeat(int x, int n)
{
unsigned int rack = x;
rack = (rack << n) | rack;
n *= 2;
rack = (rack << n) | rack;
n *= 2;
rack = (rack << n) | rack;
n *= 2;
rack = (rack << n) | rack;
n *= 2;
rack = (rack << n) | rack;
return rack;
}
```

Unfortunately this is technically undefined behaviour if the shift goes above the size of an integer. Your compiler might well accept it. But it's hard to suppress without a conditional.