CODEWITHSUNDEEP
cbitwise-operatorsbit-shift
Kurt Price
Kurt Price

Reputation: 303

Turn 0 bits to 1 bits if the bit is between low and high

Full disclosure, this is a homework problem and I do not need exact code. I am tasked with reproducing the following code while only using ~ & + <<.

int result = 0;
int i;
for(i = lowbit; i <= highbit; i++)
    result |= 1 << i;
return result;

Where lowbit and highbit are parameters between 0 and 31 inclusive. If lowbit is a larger number than highbit, return 0.

What I have tried so for is the following code

int result = 0;
int negone = ~0x0;
int first = 1 << (lowbit + negone); //the first 1 bit is at the lowbit th location
int last = 1 << (highbit + negone); //the last 1 bit is at the highbit th location
int tick = ~(first + last); //attempting to get all bits in the range of low and highbit.
result = ~(~first & ~tick); //bitwise | without using |
result = ~(~last & ~result);
return result + 1; //the first bit should always be on.

So is there something fundamental I am missing here? In addition to what I have not working this also goes over my limit of 12 operators that I am allowed to use, but I'd like to try and get it working before I even begin to limit the operators.

When I run the test script on this I get errors on most of the tests it is put against including lowbit and highbit being equal to each other. Cases where highbit is the max size and lowbit is the least size seem to work though.

Any help would be much appreciated.

Upvotes: 0

Views: 748

Answers (4)

Clifford
Clifford

Reputation: 93496

1) Create a mask with the bits low to high set:

uint32_t mask = ~(~0ul << highbit << 1) & (~0ul << lowbit)

Example: lowbit = 4, highbit = 12 (9 bits)

mask = ~(0xffffffff << 12 << 1) & (0xffffffff << 4)
     = ~(0xffff7000) & 0xfffffff0
     =   0x00001fff  & 0xfffffff0
     =   0x00001ff0

2) Apply the mask to the value to be modified, this most simply an | operation, but that is not a valid operator in this exercise, so must be transformed using De Morgan's forum:

A|B -> ~(~A & ~B) :

result = ~(~result & ~mask) ;

It is of course possible to combining the two steps, but perhaps clarity would not then be served.

Upvotes: 1

aczzdx
aczzdx

Reputation: 14

The problem could be that tick = ~(first+last) does not flip the bit from the lowbit to the highbit.

Maybe we can do something like this:

/* supposed that lowbit = 1, highbit = 2 */
uint32_t negone = ~(0u); /* negone = all 1s */
uint32_t first = negone << lowbit;  /* first = ...111110 */
uint32_t last = (1 << (highbit + 1)) + negone; /* last = ...0000111 */
uint32_t tick = last & first; /* tick = ...000110 */
result = ~(~result&~tick); /* Bitwise Or without | as you mentioned. */

It takes 11 bit operations to do this.

p.s. I am wondering why the first bit should be always on.

Edit: In order to avoid undefined operation, we should use unsigned type, like uint32_t.

Upvotes: -1

Stephan Lechner
Stephan Lechner

Reputation: 35154

The original code generates a block of 1 from lowbit on until highbit (inclusive). This can be achieved without a loop as follows:

int nrOfBits = highbit + ~lowbit + 2;  // highbit - lowbit + 1
int shift = (nrOfBits & 0x1f + 1);
int result = ~(~(1 << shift)+1) << lowbit;

The idea is that, for example a range of 8 bits filled up with 1 means a number of 255, whereas 2^8 is 256. So - as operator - is not allowed, we use 2-complement to get -256, add 1 to get -255, and turn it back to +255 using 2-complement operator ~. Then, we just have to shift the block lowbits left.

Upvotes: 0

chqrlie
chqrlie

Reputation: 144818

negone should be initialized this way:

uint32_t negone = ~0UL;

You are adding the bit number with a bit pattern in:

int first = 1 << (lowbit + negone); //the first 1 bit is at the lowbit th location
int last = 1 << (highbit + negone);

You should instead compute the 32 bit masks

uint32_t first = negone << lowbit;  // all bits below lowbit are 0, others are 1
uint32_t last = negone << highbit << 1;  // all bits above highbit are 1, other are 0

The result is obtained by masking the complement of first with last:

uint32_t result = ~first & last;

Combining the above steps gives is a direct solution with 7 operators (12 including the parentheses and the assignment), no addition, and no subtraction:

uint32_t result = ~(~0UL << highbit << 1) & (~0UL << lowbit);

I use 0UL because type unsigned long is guaranteed to have at least 32 bits, whereas type unsigned int might have just 16 bits.

Upvotes: 4

Related Questions