Permute a string using Bit-Reversal

Question

Previously, we computed the Bit-Reversal Permutation where we found how the order of indices would be permuted. In that case, we received an input n which was the order of the permutation of the indices where the length was 2ⁿ. However, this time, we are given a string of length m = 2^k for some k. Now we want to apply the permutation indices of order k to a string.

Task

Your goal is to create a function or program that given a string where the length is a power of 2, output the permutation of it using bit-reversal.

As an example, the string 'codegolf' has length 8 which is a power of 2, that is 8 = 2³. We learned in the previous challenge that the bit-reversal permutation of order 3 is [0, 4, 2, 6, 1, 5, 3, 7] which means that we select the characters from the input string using that order of indices.

Input                  Output
0 1 2 3 4 5 6 7        0 4 2 6 1 5 3 7
c o d e g o l f        c g d l o o e f

This is one possible method of solving this task. Since we do not require the order of indices as output, there may be shorter algorithms which avoid generating the indices and rely on permuting characters only.

Test Cases

Input = Output
"z" = "z"
"cg" = "cg"
"code" = "cdoe"
"golf" = "glof"
"codegolf" = "cgdlooef"
"aaaazzzz" = "azazazaz"
"LynngDaie dneers" = "Legendary Dennis"
"hieroglyphically" = "hpoaeillihglrcyy"
"Programming Puzzles N' Code-Golf" = "PliorNPGosgem zlrenda'uog  -mCzf"
"super spectacular dazzling dream" = "srenrzcrpdt sllau cg zueeaadpiam"

Rules

• This is code-golf so the shortest code wins.
• Builtins are allowed.
• The input string will only be in ASCII. The length of the input string will always be a power of 2.

Answer 1

Pyth, 9 bytes

hu+M.Tc2G

Try it online

How it works

 u       Q   fixed point: let G = input, and repeatedly replace G with
      c2G      chop G into two equal pieces
    .T         justified transpose
  +M           map concatenate
             until a duplicate is found
h            take the first (only) element of the resulting list

Answer 2

Haskell, 72 bytes

This is "permuting characters only", but is it shorter than a different approach?

s(a:b:c)|(x,y)<-s c=(a:x,b:y)
s n=(n,n)
r a|[_]<-a=a|(x,y)<-s a=r x++r y

s is a helper function to seperate the characters from even and odd positions, r is the bit reversal permutation function:

Prelude> r "codegolf"
"cgdlooef"

Answer 3

Python 3.5, 112 111 bytes:

from math import*;lambda d:''.join([d[int(bin(i)[2:].zfill(int(log2(len(d))))[::-1],2)]for i in range(len(d))])

You really start to appreciate the all in one power and compactness of Python once you start using languages like C and Java. Anyways, this is an anonymous function that you call by first naming it, and then calling it like a normal function wrapped inside the print() function.

Try It Online! (Ideone)