CODEWITHSUNDEEP
bit-manipulationbitwise-operators
Benjamin Higgins
Benjamin Higgins

Reputation: 117

Is it possible to test if a number is either even or '1', using only bitwise operators?

Is it possible to achieve using only bitwise operators, ie without logical/comparison/relation operators?

This would essentially be equivalent to the following.

(a & 1 == 0) || (a == 1)

I accept that in many languages a final equality comparison may need to be done to convert the result to a true/false value, but I am not considering that in the question. An answer which accepts an input bit array and returns the same output bit array for an even number as for '1' is essentially what I am after. Either that or a reason why it is not possible.

Upvotes: 2

Views: 813

Answers (5)

RARE Kpop Manifesto
RARE Kpop Manifesto

Reputation: 2805

Is comparing against double-logical-negate considered acceptable ?

jot 99 0 | 

((x != !!x) + x) & 1 

 (x != !!x) ^ (x & 1)    # "^" := bitwise XOR

1
2
4
6
8

10
12
14
16
18

Note : only have tested them for unsigned ints.

Upvotes: 0

Falk Hüffner
Falk Hüffner

Reputation: 5040

A method that works for any fixed (power-of-two) bit width is to use the following function which returns 1 when all bits are set and 0 otherwise:

uint32_t allOnes(uint32_t a) {
    a &= a >> 1;
    a &= a >> 2;
    a &= a >> 4;
    a &= a >> 8;
    a &= a >> 16;
    return a;
}

We can then do the check as follows:

uint32_t f1(uint32_t a) {
    return (~a & 1) | allOnes(a ^ ~uint32_t(1));
}

Upvotes: 0

John D McCalpin
John D McCalpin

Reputation: 2236

I am not entirely sure I understand what you are asking, but in the Intel64/AMD64/x86_64 instruction set, it is easy to perform a sequence of bitwise operations that will both return a value and a condition code flag that allows the proposed comparison.

Assume that the input value is in the %rax register.

MOV %rax, %r8     # replicate input value into %r8
MOV %rax, %r9     # replicate input value into %r9
AND $0x1, %r8     # AND 0x1 with the contents of %r8 and put result in %r8
XOR $0x1, %r9     # XOR 0x1 with the contents of %r9 and put result in %r9
OR  %r8, %r9      # OR %r8 with %r9 and put result in %r9

The AND operation will return 0 if the input is even, otherwise it will return 1. The XOR operation will return 0 iff the input is 0x1, otherwise it returns non-zero. The OR operation will return 0 iff both %r8 and %r9 are zero, otherwise it returns non-zero.

Each of the bitwise operations sets various condition flags. The relevant one here is called "ZF", which is set to 1 iff the result of the operation is 0.

The ZF flag set by the final operation can be used to control a conditional branch. Use "JZ" (Jump if Zero) to branch if ZF=1 (i.e., the condition is true) or "JNZ" (Jump if Not Zero) to branch if the condition is not true.

You can save the result from %r9 to memory and use it later in a comparison against zero (true) or not zero (false).

You can also act on the result without using a conditional branch instruction -- the same condition code can be used to control a conditional move instruction. The CMOVE instruction will copy an an input operand in memory or in a register to an output register iff ZF=1, or CMOVNE will perform the copy iff ZF=0. For example, you could copy the value "1" from a source register to a destination register iff the condition was true, then accumulate the destination register values into an accumulator. The accumulator will then contain the count of cases for which the comparison returned "True".

Upvotes: 1

Eraklon
Eraklon

Reputation: 4288

Although I would not recommend to do this at all, but I was able to achieve it in C, but with only making a to be anunsigned char. It could work with others too, but that would lengthen the condition.

#include <stdio.h>

int main() {
    for (unsigned char a = 0; a < 255; a++) {
        if ((~a & 1) | (1 >> (a & 0x0E | a >> 4)))
            printf ("%d is even or 1\n", a);
        else
            printf("%d is odd\n", a);
    }
    return 0;
}

(~a & 1) will yield 1 if a is even. (a & 0x0E | a >> 4) will yield 0 when a is either 1 or 0. Therefore in those cases (1 >> (a & 0x0E | a >> 4))) will be (1 >> 0) which is 1, otherwise the shift value is between 1 and 15 so making the expression 0.

My initial approach was (1 >> (a >> 1)), but soon realized this cause shift overflow, since the shift amount exceed the max possible. And not just raising that warning, but actually falsely recognize every n * 64 + 1 values as even. So the more complicated approach is there to limit the shift amount to be less than 64 by OR -ing a upper 4 bit with its lower 4 bit, but setting the LSB to 0. This resulting number is <= 15 and only 0 when a is 1 or 0 just as needed.

Upvotes: 1

phuclv
phuclv

Reputation: 41774

((a & 1) == 0) | (a == 1) works. No need to do any complex tricks

Upvotes: 2

Related Questions