-1

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.

6
  • 3
    Hint: which bits are set in a number larger than 7?
    – dbush
    Jan 25 at 18:11
  • 2
    @dbush The answer depends a good deal on whether the negative numbers are allowed or not :-) Jan 25 at 18:15
  • "[U]ses 2's complement" is a statement about how the machine represents negative integers. Are we to conclude that this is in fact a concern? That is, what is the data type of the value to be tested? int? int32_t? unsigned int? uint32_t? Something else? Jan 25 at 18:21
  • @JohnBollinger It seems like the given conditions are describing how bitwise operators work on signed numbers, since the C spec leaves that implementation-dependent.
    – Barmar
    Jan 25 at 18:24
  • 1
    I downvoted because these "How can I do task A without using obvious language features X, Y, or Z?" questions are silly puzzles which have no place in serious programming, and essentially no value for future readers. Jan 25 at 18:49

3 Answers 3

6

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));
}
0
2

>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
2
  • Note that this doesn't work for negative numbers (as stated in the answer).
    – ikegami
    Jan 25 at 18:32
  • @Fe2O3 ack! Fixed.
    – ikegami
    Jan 26 at 2:44
1

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 !, >>, & ~.

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.