Can this code be optimized?

Disable overflow checking.
 Project Properties -> Compilation -> Advanced Compilation Options -> Remove Integer Integrity Checks.
If you need overflow checking for the rest of the project, you can move the code to a new project (like a DLL) and disable overflow checking for that new project.

Also make sure you are running a release build (optimization enabled) and you are not debugging it.

EDIT: I get 8.5s (12s if I declare an array inside the For parameter that I use for testing) to call the function 50 million times. If you only get 32000, either you are using very large inputs or something is slowing down your code. For example, if you count the time inside a program and run it in a profiler, you will get incorrect results because profiling can slow down the program dramatically. Also glitches like these Slow method calls can impact performance.

I think when Recursive quoted BitArray, he meant something like this:

using System.Collections.Generic;
using System;
using System.Collections;

class Program
{
    static void Main(string[] args)
    {
        var input = new BitArray(new byte[] { 0x5A /*01011010b*/
                                        , 0xE4 /*11100100b*/ });
        var output = new List<int>();
        var offset = 1;
        foreach (var bit in input)
        {
            if (bit)
            {
                output.Add(offset);
            }
            offset++;
        }
    }
}

      

        
        
        
      

    

Speed ​​for the number of items?

Changing items?

Compile time or run time?

What are the spatial constraints?

A well-known strategy is to take a few of them and write down all combinations and their results: 0000 → 0001 → 4 0010 → 3 0011 → 3.4 0100 → 2 0101 → 2.4 0110 → 2.3 ...

Why do you want to convert from this binary representation to pick a random bit? This is unlikely to help in performance. Better group them by 8 bits, use a table telling you how many 1s are in the group, and repeat 5 times. then you know how many there are. make a random selection, then choose the selected one.

You may find that using the For Each parameter and a list initialized with at least the length of the input array is faster than an index:

If arIn.Length > 0 Then
  Dim lstOut As New List(Of Integer)(arIn.Length)
  Dim ix As Integer = 0
  For Each val As Integer In arIn
    If val = 1 Then
      lstOut.Add(ix)
    End If
    ix = ix + 1
  End If
  Return lstOut.ToArray()
Else
  Return Nothing
End If

      

        
        
        
      

    

But you will have to test it.

This is what BitArray did .

Perhaps you can compress the best performance using a lookup table. Then apply the following algorithm:

Sorry I'm not talking about VB anymore, so I'll have to write C #. Here is a snippet of all the code, since the entire lookupTable will contain 256 elements.

using System.Collections.Generic;

class Program
{
    static void Main(string[] args)
    {
        var input = new byte[] { 0x5A /*01011010b*/, 0xE4 /*11100100b*/ };
        var output = new List<int>();
        var lookupTable = new int[][] { new int[0] /*00000000b*/
                                           , new int[] { 8 }    /*00000001b*/
                                           , new int[] { 7 }    /*00000010b*/
                                           , new int[] { 7,8 }  /*00000011b*/
                                           , new int[] { 6 }    /*00000100b*/
                                           , new int[] { 6,8 }  /*00000101b*/
                                           , new int[] { 6,7,8 }  /*00000111b*/
                                          };
        int offset = 0;
        foreach (var value in input)
        {
            foreach (var position in lookupTable[(int)value])
            {
                output.Add(position + offset);
            }
            offset += 8;
        }
    }
}

      

        
        
        
      

    

If it is easy to create a prime number slightly larger than the length of your array (depending on its size, it may or may not be easy), and you don't care about a completely uniform random, then you can generate a random number in that range and generate this cycle. It should find the answer within a few iterations (depending on the density 1s). Source code in C # since I don't remember the vb syntax:

int RandomInArray(int[] ar)
{
    int p = GenerateSlightlyLargerPrime(ar.Length);

    int x = random.nextInt(p);
    int i = x;
    do
    {
       if (i < ar.Length && ar[i] == 1)
           return i;
       i = (i + x) % p;
    } while (i != x);
    return -1;
}

      

        
        
        
      

    

Note that this is not 100% uniformly random, but it should be pretty close.