1, 2, 4, 8, 16, 32 - Find Inclusion of Bit

Community Forums/General Help/1, 2, 4, 8, 16, 32 - Find Inclusion of Bit

Matt Vinyl(Posted 2011) [#1]
Hi all,

Wonder if anyone could assist with this teaser I find myself posed with at the office.

We have a field in a database that, for each record within, contains a number made from either one, or a combination of each of the numbers:

1, 2, 4, 8, 16, 32

I'm guessing this is known as 'bitwise' work? (Or sort of, as that's what it says in this particular database's schema...!) Edit: Just looked up bitwise and it is a bit (hehe) different to this.

These 'bits' can be added together in any combination, but obviously not used more than once:

1+2+4=7 Valid
8+16=24 Valid
1+1+2=4 Invalid

I need to work out if one of the numbers is 'present' in the combined total (in my case, I need to know it '8' forms part of the combination).

Now, I imagine there must be a formula of some sort to work this out? A colleague has hard-coded in 30-odd numbers from pure brute-force working it out, but I feel it must be able to be done neater. Say they add 64 as another possible bit in the future?

Any ideas? Let me know if you want me to explain further...

Last edited 2011


Ross C(Posted 2011) [#2]
Well, you'd need to convert your number to binary and mask out the bit your after. I think it's the AND command you'd be after.

30 = 0011110

If you want to check if 8 appears:

0011110
AND
0001000
would result in TRUE

indicating the presence of an 8 :)

Failing that, take the number 30.

Subtract 128 from it. Less than zero? If so, this number isn't valid.
Subtract 64 from it. Less than zero? If so, this number isn't valid.
Subtract 32 from it. Less than zero? If so, this number isn't valid.
Subtract 16 from it. Less than zero? If so, this number isn't valid.
Subtract 8 from it. Less than zero? If so, this number isn't valid.
Subtract 4 from it. Less than zero? If so, this number isn't valid.
Subtract 2 from it. Less than zero? If so, this number isn't valid.
Subtract 1 from it. Less than zero? If so, this number isn't valid.

Obviously if you subtract the value and it's not a minus, use this result for your next calculation.

30
30 -128 < MINUS result. No 128 present
30 - 64 < MINUS result. No 64 present
30 - 32 < MINUS result. No 32 present
30 - 16 < POSTIVE result. 16 present.
14 - 8 < POSTIVE result. 8 present.
6 - 4 < POSTIVE result. 4 present.
2 - 2 < POSTIVE result. 2 present.
0 - 1 < MINUS result. No 1 present

The only reason I start at 128, is thats the leftmost bit of the 8 bits.

Last edited 2011


Shortwind(Posted 2011) [#3]
[Edit: LOL, someone beat me in.]

I can give you a clue as to the solution: (By the way, these are usually referred to as bit fields or flags. So with a standard 8 bit byte, you could store 8 flags, instead of using 8 different database fields or variables in your program.)

One solution, though not elegant, Masking.

Simply put, if your looking for a specific value, 8 in your example, use masking to find out if that value is on or off.

100110 AND 1000 = 0
101001 AND 1000 = 1

There are very simple ways of doing this in a program. Matter of fact, there are many examples of exactly this in the forums. :)

Last edited 2011


Andy_A(Posted 2011) [#4]
Just use the AND bit operator




Ross C(Posted 2011) [#5]
Masking is the most elegant way of doing it.


Shortwind(Posted 2011) [#6]
I like these better. :)

Function SetBit:Int(x:Int, bit:Int) 'Set specific bit(0-31) in value(x)
	Return x | (1 Shl bit)
End Function

Function ClearBit:Int(x:Int, bit:Int) 'Clear specific bit(0-31) in value(x)
	Return x & ~(1 Shl bit)
End Function

Function ToggleBit:Int(x:Int, bit:Int) 'Toggle(on/off) specific bit(0-31) in value(x)
	Return x ~ (1 Shl bit)
End Function

Function ReadBit:Int(x:Int, bit:Int) 'Return(0/1) of specific bit(0-31) in value(x)
	Return (x Shr bit) & 1
End Function



col(Posted 2011) [#7]
Hiya,
Just in case new comers to Blitz are reading this...

Blitz3D uses 'AND' to do bitwise operations
BlitzMax uses '&' to do it. 'AND' is used as a comparison operator.

When using bit operators in both it will give return the value of the bit you are testing against. So..
Print 6 & 4 will output 4 as the result in BMax
Print 6 And 4 in B3D will do the same

Not sure on the other incarnations of Blitz as I don't own them :D

Just thought I'd say before any newbies get confused :-)

Last edited 2011


Matt Vinyl(Posted 2011) [#8]
Hi all - just wanted to say many thanks for the advice. Going to work on this today based on these suggestions. Cheers! :0)