Fastest known way to extract a single bit from a byte

[bluto32]

I have experimented with various ways of extracting a bit (at a specified position) from a byte, and have come up with a slightly convoluted way of doing this as follows:

Sub Test()
    Dim PowerOf2(0 To 7) As Byte 'Store powers of 2 for efficiency
    Dim b As Byte
    Dim ExtractedBit(0 To 7) As Byte 'Really a bit array: only takes values 0 or 1
    Dim k As Long 'Bit counter
    
    'This loop allows powers of 2 to be calculated only once at the start.
    'Referring to PowerOf2(5) thousands of times in a big loop is faster than calculating 2^5 each time.
    For k = 0 To 7
        PowerOf2(k) = 2 ^ k
    Next k
    
    b = 173
    
    For k = 0 To 7
        'Extract kth bit, where bits are numbered 0 to 7 (right to left)
        ExtractedBit(k) = -CBool(b And PowerOf2(k))
        Debug.Print ExtractedBit(k)
    Next k
End Sub

The b And PowerOf2(k) returns 0 if the k bit is not set, and 2^k if it is set.
The CBool then coverts this to False (value 0) or True (value -1) respectively.
Finally, the leading minus sign converts the Boolean into the required value of 0 (unset) or 1 (set).

In massive loops, -CBool(b And PowerOf2(k)) has proved to be faster than using anything else I have tried. (For example, testing If b And PowerOf2(k) > 0 is considerably slower.) But it looks a bit weird (no pun intended...), and I can't help but think there's probably a faster and more natural way. Is there?

Also, can a variable be defined as a bit rather than a byte? I don't want to use Boolean, since I shall be using the bits in numerical calculations.

 

[Rick Rothstein]

I suspect the \ operator is slow because performing the division (which is not a fast operation anyway), it first rounds the numerator and denominator to integers before performing the division and then rounds the resulting answer (Banker's Rounding by the way). I am not so sure the underlying code bothers to check if the numerator and denominator are integers beforehand as opposed to just rounding whatever is there (and I would assume the same for the result of the ultimate division as well).

 

[GWteB]

The code I need this in will ultimately be looping 10s or 100s of millions of bytes, so I'm hoping the 0.19 seconds can be improved upon.

I think the below code could be an improvement, especially in a time-critical environment.

It's also using the AND operator (the only logical way) but we take advantage of the CPU and memory characteristics of our machine. Apparently VBA isn't optimized in that manner so we do it ourselves. CPU and memory interact with a bandwidth of 64 bits (or 32 bits on older machines). So CPU expects a data unit of 64 bits in one go. If the requested data unit isn't on a 64 bits aligned memory address, CPU needs a few more cycles to obtain such a data unit than if it was stored aligned. Normally we don't have to worry about this, but in a time-critical environment this can make some difference. With this knowledge we don't use integer data types like Byte and Integer anymore, we simply use Longs.

In addition there's the CPU built-in phenomenon known as branche prediction. On low-level stage this can be exploited better but in VBA we could try whether we might gain some advantage, especially, as said, in a time-critical environment. So I left the inner loop out.

Finally, read access (and write access as well) on elements of an array data type results in more overhead than using constants of a Long data type. We can use them directly since VBA automatically stores integer numbers as Longs. They don't have to be predeclared.

On my 10 years old machine running your post #1 code took an average of 0.1760 seconds. The code below narrows that down to an average of 0.1055 seconds.

The code isn't "neat" but who cares, especially in a time-critical environment

Sub TestByte()      ' 0.1719 <> 0.1799
    Dim PowerOf2(0 To 7) As Byte, ExtractedBit(0 To 7) As Byte, b As Byte
    Dim k As Long, i As Long
    Dim t As Double
    b = 173
    For k = 0 To 7
        PowerOf2(k) = 2 ^ k
    Next k
    
    t = Timer
    For i = 1 To 1000000
        For k = 0 To 7
            ExtractedBit(k) = -CBool(b And PowerOf2(k))
        Next k
    Next i
    Debug.Print Timer - t
End Sub

Sub TestLong()      ' 0.1016 <> 0.1094
    Dim ExtractedBit(0 To 7) As Long, b As Long
    Dim i As Long
    Dim t As Double
    b = 173

    t = Timer
    For i = 1 To 1000000
        ExtractedBit(0) = -CBool(b And 1)
        ExtractedBit(1) = -CBool(b And 2)
        ExtractedBit(2) = -CBool(b And 4)
        ExtractedBit(3) = -CBool(b And 8)
        ExtractedBit(4) = -CBool(b And 16)
        ExtractedBit(5) = -CBool(b And 32)
        ExtractedBit(6) = -CBool(b And 64)
        ExtractedBit(7) = -CBool(b And 128)
    Next i
    Debug.Print Timer - t
End Sub

 

[bluto32]

Thanks for the detailed and hugely informative explanation; that's a considerable time saving on your PC!

For whatever reason, my PC (11 years old) is giving me 0.18-0.19 seconds on my first code, and 0.16-0.17 seconds on yours. It's still a saving, so thank you.

I'm toying between two routines for an encryption project of mine. One will pick out all the bits from various bytes thrown at it. So far, your code is the fastest. My second routine will only need one or two bits each time (so no k loop needed), and not always the same bits. Call the positions of the bits k1 and k2 (between 0 and 7 inclusive). Presumably in this case, I am stuck with having to read the k1th and k2th element from my "PowerOf2" array? Otherwise, I would need a very inefficient If or Select Case routine to check which bits were being requested?

 

[GWteB]

For whatever reason, my PC (11 years old) is giving me 0.18-0.19 seconds on my first code, and 0.16-0.17 seconds on yours. It's still a saving, so thank you.

The difference in performance increment (40% vs 11%) can be explained by the difference in characteristics of the various types of CPUs.

Presumably in this case, I am stuck with having to read the k1th and k2th element from my "PowerOf2" array? Otherwise, I would need a very inefficient If or Select Case routine to check which bits were being requested?

At that point in the process, I would prefer not to differentiate between the individual bits. This would inevitably be at the expense of performance. I imagine you're going to split tasks into separate procedures which already generates an unavoidable overhead. So I'd just extract and store all the bits at once and then read out the desired bit or bits from storage.

Sub TestProcs()

    Dim bt As Long, i As Long, t As Double
    Dim ExtractedBits(0 To 7) As Long

    Dim b3 As Long, b5 As Long

    bt = 173

'   ---------------------------- 0.1562 --------------------------
    t = Timer
    For i = 1 To 1000000
        GetAllBits bt, ExtractedBits
    Next i
    Debug.Print Timer - t
    
    b3 = ExtractedBits(3)
    b5 = ExtractedBits(5)

'   ---------------------------- 0.8242 --------------------------
    Dim PowerOf2(0 To 7) As Long
    For i = 0 To 7
       PowerOf2(i) = 2 ^ i
    Next i
    
    t = Timer
    For i = 1 To 1000000
        GetSomeBits bt, PowerOf2, ExtractedBits, Array(3, 5)
    Next i
    Debug.Print Timer - t
    
    b3 = ExtractedBits(3)
    b5 = ExtractedBits(5)
'   --------------------------------------------------------------
End Sub

Sub GetAllBits(ByVal argByte As Long, ByRef argResultBits() As Long)
    argResultBits(0) = -CBool(argByte And 1)
    argResultBits(1) = -CBool(argByte And 2)
    argResultBits(2) = -CBool(argByte And 4)
    argResultBits(3) = -CBool(argByte And 8)
    argResultBits(4) = -CBool(argByte And 16)
    argResultBits(5) = -CBool(argByte And 32)
    argResultBits(6) = -CBool(argByte And 64)
    argResultBits(7) = -CBool(argByte And 128)
End Sub

Sub GetSomeBits(ByVal argByte As Long, ByRef argResultBits() As Long, ByRef PowerOf2() As Long, ByRef argTestBits As Variant)
    Dim m As Variant
    For Each m In argTestBits
        argResultBits(m) = -CBool(argByte And PowerOf2(m))
    Next m
End Sub

 

[GWteB]

No idea how this error crept in but obviously this line

GetSomeBits bt, PowerOf2, ExtractedBits, Array(3, 5)

should look like this…

GetSomeBits bt, ExtractedBits, PowerOf2, Array(3, 5)

 

[Alex Blakenburg]

If you can figure out how to make this only look at 8 bits this has to be faster.
It is currently just slower than Rick's first method and it is looking at 32 bits.

Source is: excel vba long to bits Code Example

Function LongToBits$(ByVal n&)
    Dim i&
    LongToBits = "00000000000000000000000000000000"
    If n And &H80000000 Then
        Mid$(LongToBits, 1, 1) = "1"
        n = n And Not &H80000000
    End If
    For i = 32 To 2 Step -1
        If n And 1 Then Mid$(LongToBits, i, 1) = "1"
        n = n \ 2
    Next
End Function

I called it using this:

Sub testbits()
    Dim t As Double
    Dim i As Long
    Dim str As String
    t = Timer
    
    str = LongToBits(173)
    str = Right(str, 8)
    For i = 1 To 8
        Debug.Print Mid(str, i, 1)    
    Next i
    Debug.Print Timer - t
End Sub

 

[bluto32]

No idea how this error crept in but obviously this line

GetSomeBits bt, PowerOf2, ExtractedBits, Array(3, 5)

should look like this…

GetSomeBits bt, ExtractedBits, PowerOf2, Array(3, 5)

Thanks for your posts and advice on acquiring all the bits regardless of how many are needed later.
I'll leave the question open for now in case someone manages to improve upon the -CBool(b And ...) aspect.

 

[bluto32]

Thank you for taking the trouble to reply, Alex.
Sadly, the string manipulations seem to slow the code down quite a lot, even with a quick modification to only use 8 bits. (The input can be assumed to be a long value from 0 to 255, so the sign-bit-check at the start of LongToBits$ can be removed.)
Using recursive integer division (n = n \ 2 etc.), it is more efficient to just put the results of n And 1 directly into long variables than into a single string, only to extract the bits from the string later.

 

[GWteB]

Thanks for your posts and advice on acquiring all the bits regardless of how many are needed later.

My pleasure.

I'll leave the question open for now in case someone manages to improve upon the -CBool(b And ...) aspect.

With just using VBA this is the closest as you can get, I'm afraid. In that regard I agree with @Eric W.
VBA is not equipped for this kind of operation. Any alternative (like eg bit = -(0 < (b And ...)) doesn't increase performance.

FYI, at the CPU level, it would also take multiple instructions to isolate each individual bit of a BYTE / WORD / DWORD / QWORD. On Intel platform that would be the AND instruction followed by multiple repetitions of (optional and per bit) BT (bit test instruction), RCL/RCR/ROL/ROR (rotate instructions) or SHL/SHR/SAL/SAR (shift instructions) and some register/memory move instructions.
Although, compared to VBA, this would perform of course lightning fast.

 

[bluto32]

Thanks - I'll settle for the -CBool kludge and mark this as solved as far as VBA goes.

A little off-topic to finish, but my quest for the Holy Grail may have only just started... Suppose I wanted to improve the speed further and also create a stand-alone executable for my encryption routine, which needn't have a GUI: a DOS command executable would be fine. What programming language would you recommend? Preferably something free. The code wouldn't actually interact with Excel at all; it would just need to be very fast with bit operations and be able to read/write files. My only experience is with (1) ZX Basic from 1982(!!!) and (2) VBA for Excel. But I'd be willing to learn something new .