Tell me more ×
Programming Puzzles & Code Golf Stack Exchange is a question and answer site for programming puzzle enthusiasts and code golfers. It's 100% free, no registration required.
up vote 9 down vote favorite

Create a program that computes the hamming weight of a string. Winner is the program with the lowest hamming weight.

Rules:

  • Hamming weight for an ASCII character is defined as the total number of bits set to 1 in its binary representation.
  • Assume input encoding is 7-bit ASCII, passed through whatever input mechanism is normal for your language (e.g. stdin, args, etc.)
  • Output the result, as a number, to stdout or whatever default/normal output mechanism your language uses.
  • It should go without saying, but you have to be able to actually run the program, in real life, for it to be a valid solution.
  • Winner is the solution whose code has the lowest hamming weight.
  • Sorry, no solutions in whitespace for this one! Ok, you can code in whitespace now I've sorted out the rules :)

Per-character examples:

char |  binary  | weight
-----+----------+-------
a    | 01100001 | 3
x    | 01111000 | 4
?    | 00111111 | 6
\x00 | 00000000 | 0
\x7F | 01111111 | 7
share|improve this question
if we take 0x20/ASCII 32 as the reference, isn't the humming weight of hello world 10 rather than 11? – w0lf Jun 7 '12 at 13:11
Why is the weight of hello world 11? Only 10 characters are different from a space. Also - a program's Hamming weight seems to be just its length, excluding spaces. Not so different from normal code golf. – ugoren Jun 7 '12 at 13:12
Sorry, I totally screwed this up. Wikipedia's hamming weight article is rather misleading, and I totally fubar'ed the rules. Re-writing now. Update: Ok, re-written to define it as the number of bits set to 1 in the ASCII string, sorry for the screw-up. – Polynomial Jun 7 '12 at 13:16
@ugoren A solution with lower-value ASCII characters has a lower hamming weight. – Polynomial Jun 7 '12 at 13:18
Now it all makes sense. USE UPPERCASE, BEWARE OF ~ AND o. – ugoren Jun 7 '12 at 13:22
show 6 more comments

9 Answers

up vote 7 down vote

J, weight 34

+/,#:a.i.

Usage - place the string to be measured in quotes at the end:

   +/,#:a.i.'+/,#:a.i.'
34

Alternatively, taking input from the keyboard (weight 54):

   +/,#:a.i.1!:1[1
hello
21
share|improve this answer
There's only one way to write this :) – ephemient Jun 7 '12 at 14:22
up vote 5 down vote

J, 39

+/,#:a.i:]

This is a function taking one argument. (Or replace ] with the string directly; as Gareth notes, that brings the cost down to 34.)

   +/,#:a.i:] 'hello world'
45
   +/,#:a.i:] '+/,#:a.i:]'
39
share|improve this answer
Great minds think alike. :-) – Gareth Jun 7 '12 at 14:20
up vote 4 down vote

Golfscript 84 72 58

{2base~}%{+}*

(thanks to Howard and Peter Taylor for their help)

Input: the input string has to be on the stack (passed as command line argument, or simply placed on the stack).

In case you run it from the command line, make sure you use echo -n, otherwise the trailing newline will also be counted.

Output: prints the hamming weight value to the console

The program can be tested here.

share|improve this answer
1  
Is Golfscript case-sensitive? If not, you can save a few bits by using BASE instead of base. Update: Just checked, BASE doesn't work. Good solution :) – Polynomial Jun 7 '12 at 13:40
@Polynomial I tried that after seeing your TEST/test comment :) But it doesn't work. – w0lf Jun 7 '12 at 13:43
You can get rid of {...}2* by applying 2base~ in the first place. Gets score down to 72. – Howard Jun 7 '12 at 14:03
@Howard thanks for this great tip! I've applied it in my answer. – w0lf Jun 7 '12 at 14:14
Your test mechanism is wrong, because you've forgotten an important limitation of your Web GolfScript page. You should have a ; before the string which you substitute for stdin, so that (; is unnecessary. Then Howard's observation gets it down to 65. – Peter Taylor Jun 7 '12 at 14:18
show 2 more comments
up vote 4 down vote

QBasic, 322 311 286 264

H$=COMMAND$
FOR A=1 TO LEN(H$)
B=ASC(MID$(H$,A,1))
WHILE B>0
D=D+B MOD 2
B=B\2
WEND
NEXT
?D

Kind of the right tool for the job, still sucks of course.

share|improve this answer
1  
+1 for using one of my favourite languages of all time. It's the first language I learnt to code in on a PC. – Polynomial Jun 7 '12 at 20:09
up vote 2 down vote

C, weight 322 263 256

Does the hamming weight of the hamming weight count?

main(D,H,A)char*A,**H;{for(A=*++H;*A;A+=!(*A/=2))D+=*A%2;printf("%d",D-2);}

Used mostly standard golfing techniques.
A single loop calculates weight (shifting right and adding until zero) and scans the string (advances pointer when zero reached).
Assuming D is initialized to 2 (single parameter).

Hamming weight specific optimizations:
1. ABDH, with weight 2 each, used for names.
2. *++H preferred over H[1].

share|improve this answer
Hah, I utterly failed to understand your first sentence until just now. – breadbox Jun 8 '12 at 3:35
You can get the score down to 230 by outputting the result as an unary number: main(D,H,A)char*A,**H;{for(A=*++H;*A;A+=!(*A/=2))if(*A%2)printf("@");} – schnaader Jun 9 '12 at 0:29
@schnaader, I never knew @ was a digit in the unary system. I thought it only uses 0..0. But if you want to go this, way, printf("@"+*a%2) is shorter. – ugoren Jun 10 '12 at 6:19
@ugoren: Depends on the convention/definition of unary. E.g. en.wikipedia.org/wiki/Unary_numeral_system does use tally marks and says "There is no explicit symbol representing zero in unary as there is in other traditional bases". – schnaader Jun 10 '12 at 9:54
@schnaader, OK, but I think it's stretching the requirement "as a number" too far. – ugoren Jun 10 '12 at 10:11
up vote 2 down vote

Perl, 80 (22 chars)

Done and done:

perl -0777nE 'say unpack"%32B*"'

Or here's an alternate version with a weight of 77 (21 chars):

perl -0777pE '$_=unpack"%32B*"'

I don't like that version as much, though, because its output omits the final newline.

To calculate the weight, I'm assuming that I'm counting characters in the usual way (excluding the perl -e/-E, but including other option characters). If for some reason people complain about this, then the best I can do without options is 90 (26 chars):

$/=$,,say unpack"%32B*",<>

Sample usage:

$ perl -0777nE 'say unpack"%32b*"' rickroll.txt
7071

Boom.

share|improve this answer
up vote 2 down vote

Python, 189

print sum(bin(ord(A)).count("1")for A in raw_input())
share|improve this answer
The Python 3 equivalent, print(sum(bin(ord(A)).count('1')for A in input())), has a score of 180. – dan04 Jun 8 '12 at 3:42
1  
@dan04: Use double quotes instead of single for 176. – Keith Randall Jun 8 '12 at 3:56
up vote 2 down vote

Unary 0

You all knew it was coming. First the BrainFuck program:

,[[>++[>>+>+<<<-]>>>
[<<<+>>>-]>>[-]<<<<<<[>>>>+>>+<<<<<<-]>>>>>>
[<<<<<<+>>>>>>-]<<<[>>+>+<<<-]>>>[<<<+>>>-]
[-]<<[>>[-]<[>[-]+<[-]]<[-]]>[-]>[<<<<<<->>>->>>
[-]<<<<<<[>>>>+>>+<<<<<<-]>>>>>>[<<<<<<+>>>>>>-]<<<
[>>+>+<<<-]>>>[<<<+>>>-][-]<<[>>[-]<[>[-]+<[-]]<[-]]>[-]>]<<<<<<
[>>+<[>>+>+<<<-]>>>[<<<+>>>-]>>[-]<<<<<<[>>>>+>>+<<<<<<-]>>>>>>
[<<<<<<+>>>>>>-]<<<[>>+>+<<<-]>>>[<<<+>>>-][-]<<[>>[-]<[>[-]+<[-]]<[-]]> 
[-]>[<<<<<<->>>->>>[-]<<<<<<[>>>>+>>+<<<<<<-]>>>>>>[<<<<<<+>>>>>>-]<<<
[>>+>+<<<-]>>>[<<<+>>>-][-]<<[>>[-]<[>[-]+<[-]]<[-]]>[-]>]<<<<<<]>>>
[>+>+<<-]>>[<<+>>-][-]+<[>[-]<<[<<->>-]<<[>>+<<-]>>>[-]]>[<<<+<[-]>>>>
[-]]<<[->>>>+<<<<]<[-<<+>>]<<],]>>>>>>>.

I added newlines to make it "readable" but it has a Hamming weight of 4066. It works by repeatedly getting the quotient/remainders of an input string and adding up all the remainders. Of course should you run it on itself you get: 226 (4066 % 256) (technically \xe2) so clearly it rules itself the winner.

Now we convert it to Unary and get

000 ... 9*google^5.9 0's ... 000

We use a unary implementation with NULL characters \x00 for '0' and boom, hamming weight of 0.

Bonus question: For what ASCII characters c can you run this program on a string consisting on N repitions and have it output that character. (E.G. a string of 32 spaces gives a space). What values of N work (either an infinite number of them will work, or none will).

share|improve this answer
I'm not sure I understand this solution. The brainfuck program has a huge hamming weight. Does Unary accept null bytes as a program, or would you need to re-implement Unary? If it's the latter, it's not really a valid solution - anyone could just say "I define a programming language where any single input byte gives {result}", and win every code golf challenge on the site. – Polynomial Jun 8 '12 at 10:08
A null character Unary would be fine. All you need is an EOF to say stop counting. In fact here's some pseudo-C to read that file: main(){ bignum Unarynum = 0; int c; while(EOF!=(c=readchar())){ Unarynum++; } return Unarynum; } Doesn't matter at all what you choose to be your Unary char (as long as it isn't EOF). – walpen Jun 8 '12 at 12:02
I'm still not convinced it's the former category, rather than the latter. – Polynomial Jun 8 '12 at 12:12
2  
If you can't actually run it, it's not really a solution. – Polynomial Jun 8 '12 at 12:33
2  
As Carl Sagan once said: "If you wish to calculate the hamming weight of a string, you must first invent 10^500 universes." (billions and billions, even) – walpen Jun 8 '12 at 23:13
show 1 more comment
up vote 1 down vote

Scala 231

readLine().map(_.toInt.toBinaryString).flatten.map(_.toInt-48)sum

Selftesting code:

"""readLine().map(_.toInt.toBinaryString).flatten.map(_.toInt-48)sum""".map(_.toInt.toBinaryString).flatten.map(_.toInt-48)sum

with selftesting modification.

share|improve this answer
It's weight 495, not 231. You can't get weight 231 with 126 chars - that's an average of less than 2, and all printable chars (except @ and space, which you don't use) have weight 2 at least. – ugoren Jun 7 '12 at 20:27
@ugoren: But it's only 65 chars. The program is printed nearly twice: Once the code to calculate the hamming weight, and a second time as static input to calculate it for the program. But the calculating part is missing the "readLine()" in front, because it takes the literal input. I tried to clarify the answer itself. – user unknown Jun 7 '12 at 23:15

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.