CODEWITHSUNDEEP
algorithmbinary
lufc
lufc

Reputation: 2040

Algorithm help: Calculate binary possibilities whilst ignoring zero bits

I'm trying to develop an algorithm to test if binary number A is a "sub-number" of binary number B.

A is a sub-number of B if it can be created using only the "1" bits from B.

For example:

If B = Decimal 5 = Binary 101 Then A = {100,001,101} because they use only the bits which were active in B.

If B = Decimal 8 = Binary 1000 Then A = {1000}

If B = Decimal 7 = Binary 1110 Then A = {1000,0100,0010,1100,0110,1010,1110}

n(A) = (2^(number of active bits))-1

How can I develop a test for whether a decimal number x is in the set A for decimal number B? E.g. IsSubNumber(A,B)

IsSubNumber(1,7) = true IsSubNumber(2,8) = false

Does this make sense?

Thanks!

Upvotes: 1

Views: 69

Answers (2)

Jean Logeart
Jean Logeart

Reputation: 53829

A is a subnumber of B if bitwise-and between A and B is equal to A.

Example: 1000 & 1110 = 1000, 1010 & 1110 = 1010, 101 & 101 = 101...

In java:

boolean isSubNumber(int a, int b) {
    return (a&b) == a;
}

Upvotes: 2

turingcomplete
turingcomplete

Reputation: 2188

Simply, if bit i in A is a 1, then it also must be 1 in B. So simply loop over A, if the current bit is a 1, then check the corresponding bit in B, if it's not a 1, then output false, otherwise keep on testing the next bit in A until you find a mismatch, or you run out of bits.

Upvotes: 1

Related Questions