PDA

View Full Version : Find lowest bit in an integer



mikerickson
10-28-2007, 05:18 PM
I would like to find the lowest bit of an integer.

Since 6 = 0110 , the lowest bit is the 2's bit, it returns 1.
Since 12= 1100, the lowest bit is 4 = 2^2. The answer I want is 2.
Since 11 = 1011, the lowest bit is 1 = 2^0. Answer is 0.

If I was looking for the highest bit, I could use Int(Log(N)/Log(2)).
Is there a similar way to find the lowest bit or is looping through
(N And (2^i)) the best way to go.

The purpose is that I am using an array of Boolean values. The mapping from Boolean arrays to binary numbers allows me to
1) use less memory to store the "arrays"
2) use arithmetic processes rather than looping through array indices. IF I can arithmetize the procedures I am use. Specificaly, for this post, (firstFalseInArray) ~~ first bit of NOT(arrayAsBinary)

Bob Phillips
10-28-2007, 06:25 PM
Bit mechanical but it works



Do While target = (target \ 2) * 2
cnt = cnt + 1
target = target \ 2
Loop

mikerickson
10-28-2007, 06:55 PM
That's a faster version of the loop I was hoping to avoid.

Paul_Hossler
10-29-2007, 06:24 AM
Here's some bit manipulation functions that I use to wrap the AND and OR VBA functions

You could 'in-line' the logic if you wanted to tune it

Paul




' Name Description
' --------------------------------------------------------------------
' BitMask Returns a mask used by the other routines to set or test
' the value of a bit in a variable.
' BitSet Turns a bit "on" or "off".
' BitFlip Changes the state of a bit.'
' BitTest Returns the state of a bit.
'
'The BitTest and ArrayBitTest functions return TRUE (-1) if the bit is 1
' and FALSE (0) if the bit is 0 (zero).

Function BitMask(N As Long) As Long
On Error GoTo ReturnZero
BitMask = Array( _
0&, 1&, 2&, 4&, 8&, 16&, 32&, 64&, 128&, _
256&, 512&, 1024&, 2048&, 4096&, 8192&, 16384&, 32768, _
65536, 131072, 262144, 524288, 1008576, 2097152, 4194304, _
8388608, 16777216, 33554432, 67108864, 134217728, _
268435456, 536870912, 1073741824)(N)
Exit Function

ReturnZero:
BitMask = 0
End Function

Sub BitSet(X As Long, ByVal N As Long)
X = X Or BitMask(N)
End Sub

Sub BitClear(X As Long, ByVal N As Long)
X = X And Not BitMask(N)
End Sub

Sub BitFlip(X As Long, ByVal N As Long)
X = X Xor BitMask(N)
End Sub

Function BitTest(X As Long, ByVal N As Long) As Boolean
BitTest = (X And BitMask(N)) <> 0
End Function

Bob Phillips
10-29-2007, 06:41 AM
Perhaps I am missing something, but Bitmask seems a bit of overkill.

Doesn't



(N-1)^2


work just as well with much less fuss?

Paul_Hossler
10-29-2007, 08:09 AM
XLD --

1. Some times I over-achieve just for the thrill of it :rofl:

2. Probablely doesn't make any performance difference, but I stay away from the exponentation operator whenever possible. Returning a value based on an array index seems faster (on paper anyway) (Opinion).

Paul

Bob Phillips
10-29-2007, 08:44 AM
No opinion on performance, but for sheer maintainability, it looks horrible to me.

mikerickson
10-29-2007, 12:49 PM
Speed is the only objection that I can see to 2^n method. Since the arithmentic And and Or etc only works on integers (math not data type) roundoff error shouldn't be a problem.