# How to efficiently count all powers of 2 in a given set of numbers in vb.net?

Every integer can be expressed in powers of 2. You know this as the binary system

Assume you are given a set of k numbers (0 < k < 2^n). You want to decide for this set whether every integer power of 2 up to 2^(n-1) occurs at least m times

One example:

n = 7 (2^n = 128, )
k = 5
set =
{100,
91,
88,
63,
44}
m = 3

Solution:
Consider the binary representation of the set for up to n(=7) digits:
set = {
1100100
1011011
1011000
0111111
0101100
}
sum up the columns
{3,3,3,4,3,2,2} -> result the set failed, because 2 < m


This is so far my best(fastest) algorithm(, written for vb.net):

Private Function Check(arr As Integer(), n As Integer, m as Integer) As Boolean
For i = n - 1 To 0 Step -1
Dim columnCheck = 0
For j = 0 To arr.Length - 1
If (arr(j) And (1 << i)) <> 0 Then columnCheck += 1
Next
If columnCheck < m Then Return False
Next
Return True
End Function


maximum size of the elements of arr need to checked before entering.

Do you have better ideas?

• It seems that we don't need n and k as input because we already have a correct set of numbers Commented Mar 14, 2023 at 15:21
• I dont have k as input. n is needed for the loop, however you can calculate this from the array. Although I dont want to do that, because im checking the different inputs not randomly, but I assume a constant n over multiple iterations. So I dont want to calculate it everytime. Assume set is generated from n not the other way around, so you know n always before u know the set. Commented Mar 14, 2023 at 15:41
• You probably should add the tips tag. Commented Mar 14, 2023 at 15:43
• Either I should or I shouldnt, I dont see probability associated with this^^ Commented Mar 14, 2023 at 15:48
• I think the relative sizes of m, n, and k matter a lot for performance. For instance, is m roughly on the scale of k, or is it small? Do you know in what regime you're working in?
– xnor
Commented Mar 14, 2023 at 21:49