Bit repeater

Based on a real problem. Given a large string of bits, our goal is to duplicate all of them. So 0010 becomes 00001100. Next even day we will look at ways to do this on whole files quickly, but today I want to show you the first solution I came up with (yes this is actually how my brain works). Before touching a whole file I wrote a function to map a single 32 bit integer to a 64 bit integer with all the bits repeated once. The function is shown bellow:

const L: usize; const MASK1: [u64; L]; const MASK2: [u64; L]; pub fn double(x: u32) -> u64 { let mut res = 0; for i in 0..L { let y = (x as u64) & MASK1[i]; res |= (y * y) & MASK2[i]; } res | (res << 1) }

This seemed like the obvious place to start since doubling a bit's position is kinda like squaring the whole number. Unfortunately I seem to have forgotten the Values in MASK1 and MASK2. Can you help me find the shortest MASK1 and MASK2 that will make this function work? Feel free to use code to find these.

Enter the values for the masks in two lines comma separated. The masks must have the same length. You may use base 10 or the 0x prefix for hex

Solution:




Need a hint? Click below:

The last line doubles bits to their neighbors, so the first part just needs to spread them out. What does squaring a power of 2 do in binary?

More hints? Click below:

Why does squaring a non power of 2 not always work? How many bits can you fit into one number without it breaking?

Final Hint? Click below:

The naive greedy algorithm just works.