a grid like:

  . . . x * * * (row 2, bit value 4) 
  . . . * * * * (row 1, bit value 2)
  . * * . . . * (row 0, bit value 1)
[download]

would have $dim = 3 (the height), $args = [ 1, 2, 1, 0, 0, 0, 2, 1 ] (where for example $args->[6] == 2 because there are two columns with stars in the pattern 0b110, ie stars in rows 1 and 2 but not in row 0), and a location ('x' marks the spot) with $height = 2 and $v = 2 - the height represents the row number of the 'x', and $v represents the bit-pattern of the stars in the column where the 'x' is. Note that there is never a star at the same point as the 'x'.

What the function needs to do is to find a transformation of the bits such that the column with the 'x' moves all its stars to the bottom:

  # swap rows 0 and 1
  . x . . * * *
  . . * * . . *
  . * . . * * *
  $args = [ 1, 1, 2, 0, 0, 2, 0, 1 ]
  $height = 2, $v = 1
[download]

.. and moves the 'x' down to just above the highest star in its column:

  # .. and now swap rows 1 and 2
  . . . . * * *
  . x * * . . *
  . * * * . . *
  $args = [ 1, 1, 0, 2, 2, 0, 0, 1 ]
  $height = 1, $v = 1
[download]

.. and returns the new $height and $args.

(Oh, I should have warned you: I suspect I'm finding it difficult to come up with a better algorithm for the same reason as I'm finding it difficult to explain this.)

Here's the code I'm using right now:

sub rearrange {
  my($dim, $height, $v, $args) = @_;
  my @bitmap = (0 .. $dim - 1);
  my($ones, $zeros) = (0, $dim - 1);

  # find holes in the ones looking from the bottom and plugs
  # in the zeros looking from the top, then swap them
  while ($ones < $zeros) { 
    ++$ones , next if ($v & (1 << $ones )) != 0;
    --$zeros, next if ($v & (1 << $zeros)) == 0;
    @bitmap[$ones, $zeros] = @bitmap[$zeros, $ones];
    ++$ones;
    --$zeros;
  } 
  ++$ones if $ones == $zeros && ($v & (1 << $ones)) != 0;
  # $ones is now a count of the number of 1-bits

  # may need an extra swap to get the 'x' at the right height
  if ($bitmap[$height] != $ones) { 
    my($lowest) = grep $bitmap[$_] == $ones, 0 .. $dim - 1;
    @bitmap[$height, $lowest] = @bitmap[$lowest, $height];
  }

  # we now know what row should go where, so build and return the mapp
+ed result
  my @invmap = sort { $bitmap[$a] <=> $bitmap[$b] } 0 .. $dim - 1;
  my @vmap = (0);
  for (0 .. $dim - 1) { 
    my $mapped = 1 << $invmap[$_];
    push @vmap, map $_ + $mapped, @vmap;
  } 
  ($bitmap[$height], [ @$args[ @vmap ] ]);
}
[download]