sgoldburg sgoldburg - 1 month ago 21
C Question

Optimize Boolean Mask Assignment

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)
. If there is some overlap between x's and y's bits, value is set to 0, otherwise value is left alone.

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
data in some capacity help ?

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.

Comments