If you’re on Facebook (who isn’t these days?), you’ll notice a recruiting ad/new programming puzzle for Facebook in your news feed this morning. These guys actually have some pretty interesting puzzles. (The ads are always prefixed with "Can you solve this programming puzzle?" which always reads to me in a sly and somewhat condescending tone, "Betcha you can’t..") This new puzzle, known as Prime Bits, in particular, is fairly simple:
Define P(x) as true if the number of 1 bits set in the binary representation of x is prime, false otherwise.
Implement the function uint64 prime_bits(uint64 a, uint64 b) where prime_bits returns the number of values between a and b inclusive for which P(x) is true.
I sometimes like to take problems that other people are attempting to solve and attempt to solve them in a less powerful language. More often than not, people needlessly pick a powerful language just because they are comfortable with it and end up with some bloated solution (like using a jackhammer to dig a hole to plant a seed). But trying to accomplish the same objective in a less advanced language can actually come up with some pretty neat solutions sometimes, and it actually forces you to *think*. Imagine that.
Now this implementation won’t get you a job at Facebook (this solution is much too simple and batch scripting isn’t on their list of approved languages), so I figure I’m safe in posting this here. Chances are that if you have to copy this solution you don’t know enough to get hired anyway. (According to Mark Zuckerberg, you have to be young and technical. "Young people are just smarter." Great article, by the way.)
@echo off
setlocal ENABLEEXTENSIONS
setlocal ENABLEDELAYEDEXPANSION
setlocalREM Author: DevDuck
REM Date: March 29, 2007set A=%1
set B=%2if "%A%"=="" ( goto :USAGE )
if "%B%"=="" ( goto :USAGE )
if %A% GTR %B% ( goto :USAGE )
if %A% LSS 0 ( goto :USAGE )
if %B% LSS 0 ( goto :USAGE )set CUMULATIVE=0
for /l %%i in (%A%,1,%B%) do (
call :PX %%i
)
echo %CUMULATIVE%goto :EOF
:PX
REM Number of bits set:
REM 0: 0
REM 1: 1 2 4 8
REM 2: 3 5 6 9 A C
REM 3: 7 B D E
REM 4: Fset NUM=%1
set COUNT=0
REM 2^64 has max 16 hex digits, but since 2^32 is the largest num size
REM for batch scripts, we use 8
for /l %%i in (1,1,8) do (
if !NUM! GTR 0 (
set /a REMAINDER = !NUM! ^& 15
for %%j in (1 2 4 8) do (
if !REMAINDER! == %%j ( set /a COUNT += 1 )
)
for %%j in (3 5 6 9 10 12) do (
if !REMAINDER! == %%j ( set /a COUNT += 2 )
)
for %%j in (7 11 13 14) do (
if !REMAINDER! == %%j ( set /a COUNT += 3 )
)
if !REMAINDER! == 15 ( set /a COUNT += 4 )
)
set /a NUM ^>^>= 4
)REM There are only 18 prime numbers less than 64.
for %%i in (2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61) do (
if %COUNT% == %%i (
set /a CUMULATIVE += 1
)
)goto :EOF
:USAGE
echo Usage:
echo %0 ^<A^> ^<B^>
echo %0 returns the number of values between A and B for which P(x)
echo is true. P(x) returns true if the # of 1 bits set in the binary
echo representation of x is prime.
goto :EOF
Not bad, eh? How does this work? Simple. First, it iterates through each number in the range specified in the user. For each number, it first counts the number of bits set in four bit chunks (2^4, or 16). Note that the (really really) simple solution would have been to count each individual bit by dividing by two/right-shifting by 1 (much like you learnt in high school)–this way is just a little bit faster (.. although arguably it isn’t since you can’t jump to the next iteration of a for loop a la "continue". There are numerous ways to do this part more efficiently and I’ll leave that as an exercise to the reader (ie: "I don’t feel like doing it.")). Finally, it checks if the count is a prime number, and if it is, it increments the cumulative number count. Also, due to the limitation of batch scripts, precision is limited to 32-bits (although this should be a very simple port to Perl).
That was fun. Any other cool solutions out there?
red hot place 