For this question, it asks to return 1 if the argument is greater than 7, and 0 otherwise.

For example, if x is 8, the function will return 1. If x is 7, the function will return 0.

The only legal operators allowed are (! ~ & ^ | << >>), which forbids the use of anything else such as -, for loops, while loops, if statements, etc.

We can assume the system uses 2's complement and a 32 bit representation of integers, performs right shifts arithmetically, and has unpredictable behavior when shifting an integer by more than the word size.

I know that subtracting without using the - operation can be done with ~, but I don't know how to think of this one logically to be honest.

CodePudding user response：

In binary, the decimal number 7 is 111. Hence, a number which is greater than seven will always have a more significant bit set than the most significant bit in the binary representation of 7 (i.e. bit 3 when numbering from 0) set. So, if you are dealing only with unsigned numbers then this test is sufficient:

int bitwise_is_n_gt_7 (unsigned int value)
{
    return value & 0xFFFFFFF8; // assuming size 32-bits adjust as  necessary
}

If you are dealing with signed numbers you have to also deal with the possibility that a number is negative, so you then test for:

int bitwise_is_n_gt_7 (int value)
{
    return (!!(value & 0x7FFFFFF8) & !(value & 0x80000000));
}

CodePudding user response：

>7 is the same as ≥8.

You can check if a positive number is ≥ another positive number using integer division. It's larger if the result is non-zero.

Division isn't a "bit operation", but eight is a power of two, and there's a "bit operation" that's defined as a division by a power of 2: >>

So we could use:

n >> 3

Right-shifting a positive integer by three removes the three least-significant bits while moving the others. But we don't care if the others are moved or not.

So we could also use:

n & ~7

CodePudding user response：

If an unsigned number is 7 or less, then the only bits that will be set will be bits that represent 4 or 2 or 1.
The next higher bit represents 8, which is greater than 7.

So, if you "turn off" the lowest 3 bits (which represent 4, 2, and 1), with masking, and check if any bits still remain on, then the original number was 8 or greater.

if (number & ~0b0111) // Turn OFF the lowest 3 bits, keep all the others.
{
    printf("Number is 8 or Greater\n");
}
else 
{
    printf("Number is 7 or less\n");
}

Using the 0b prefix is non-standard (but very common in many compilers), so you might choose to replace 0b0111 with 0x07, or just plain-old 7 instead:

if (number & ~7)  { /* number is greater than 7 */ }

Example Code:

#include <stdio.h>

int main(void) {
    for(int i=0; i<30;   i)
    {
        printf("%d is %s 7\n", i, i&~7? "greater than" :"less than (or equal to)");
    }
    return 0;
}

Output

0 is less than (or equal to) 7
1 is less than (or equal to) 7
2 is less than (or equal to) 7
3 is less than (or equal to) 7
4 is less than (or equal to) 7
5 is less than (or equal to) 7
6 is less than (or equal to) 7
7 is less than (or equal to) 7
8 is greater than 7
9 is greater than 7
10 is greater than 7

Starting with this basic concept, and to handle negative numbers, you need to check if the "sign-bit" is set. If it is set, the number is automatically negative, and automatically less than 7.

Breaking it all down:

#include <stdio.h>
#include <stdbool.h>

int main(void) {
    for(int i=-10; i< 10;   i)
    {
        bool is_negative_bit_off = !(i>>31);
        bool is_bit_8_or_higher_set = !!(i&~7);

        if (is_negative_bit_off && is_bit_8_or_higher_set)
        {
            printf("%d is greater than 7\n", i);
        }
    }
    return 0;
}

And then simplifying it:

int main(void) {
    for(int i=-10; i< 10;   i)
    {
        bool num_greater_than_7 = !(i>>31) & !!(i&~7);

        if (num_greater_than_7)
        {
            printf("%d is greater than 7\n", i);
        }
    }
    return 0;
}

So the final expression / answer to your question is:

bool num_greater_than_7 = !(i>>31) & !!(i&~7);

(read as, "Is the Number Positive? And is the Number greater than 7?")

Operators used are !, >>, & ~.