Population count: Difference between revisions
(Perl 6 entry) |
(→{{header|Perl 6}}: show faster version) |
||
Line 51: | Line 51: | ||
0 3 5 6 9 10 12 15 17 18 20 23 24 27 29 30 33 34 36 39 40 43 45 46 48 51 53 54 57 58 |
0 3 5 6 9 10 12 15 17 18 20 23 24 27 29 30 33 34 36 39 40 43 45 46 48 51 53 54 57 58 |
||
1 2 4 7 8 11 13 14 16 19 21 22 25 26 28 31 32 35 37 38 41 42 44 47 49 50 52 55 56 59</pre> |
1 2 4 7 8 11 13 14 16 19 21 22 25 26 28 31 32 35 37 38 41 42 44 47 49 50 52 55 56 59</pre> |
||
That's the convenient way to write it, but the following avoids string processing and is therefore about twice as fast: |
|||
<lang perl6>sub population-count(Int $n is copy where * >= 0) { |
|||
loop (my $c = 0; $n; $n +>= 1) { |
|||
$c += $n +& 1; |
|||
} |
|||
$c; |
|||
}</lang> |
|||
=={{header|Python}}== |
=={{header|Python}}== |
Revision as of 17:50, 12 March 2014
population count, evil numbers, odious numbers
definitions
The population count (also known as pop count) is the number of 1's (ones) in the binary representation of an non-negative integer.
- I.E.: 5 (which is 101 in binary) has a population count of 2.
- Population counts are normally restricted to non-negative integers, which will be the case for this Rosetta Code task.
Evil numbers are non-negative integers that have an even number of 1s (ones) in their binary representation of the number.
Odious numbers are positive integers that have an odd number of 1s (ones) in their binary representation of the number.
task requirements
- write a function (or routine) to return the population count of a non-negative integer.
- all lists below should start with 0 (zero).
- display the pop count of the 1st thirty powers of 3 (30 31 32 33 34 ···).
- display the 1st thirty evil numbers.
- display the 1st thirty odious numbers.
- display each list of integers on one line (which may or may not include a title).
See also
- Sequence A000069 odious numbers on The On-Line Encyclopedia of Integer Sequences.
- Sequence A001969 evil numbers on The On-Line Encyclopedia of Integer Sequences.
- Entry evil number on The Eric Weisstein's World of Mathematics (TM).
- Entry odious number on The Eric Weisstein's World of Mathematics (TM).
PARI/GP
<lang parigp>vector(30,n,hammingweight(3^(n-1))) od=select(n->hammingweight(n)%2,[1..100]); ev=setminus([1..100],od); ev[1..30] od[1..30]</lang>
- Output:
%1 = [1, 2, 2, 4, 3, 6, 6, 5, 6, 8, 9, 13, 10, 11, 14, 15, 11, 14, 14, 17, 17, 20, 19, 22, 16, 18, 24, 30, 25, 25] %2 = [3, 5, 6, 9, 10, 12, 15, 17, 18, 20, 23, 24, 27, 29, 30, 33, 34, 36, 39, 40, 43, 45, 46, 48, 51, 53, 54, 57, 58, 60] %3 = [1, 2, 4, 7, 8, 11, 13, 14, 16, 19, 21, 22, 25, 26, 28, 31, 32, 35, 37, 38, 41, 42, 44, 47, 49, 50, 52, 55, 56, 59]
Perl 6
<lang perl6>sub population-count(Int $n where * >= 0) { [+] $n.base(2).comb }
say map &population-count, 3 «**« ^30; say (grep { population-count($_) %% 2 }, 0 .. *)[^30]; say (grep { population-count($_) % 2 }, 0 .. *)[^30];</lang>
- Output:
1 2 2 4 3 6 6 5 6 8 9 13 10 11 14 15 11 14 14 17 17 20 19 22 16 18 24 30 25 25 0 3 5 6 9 10 12 15 17 18 20 23 24 27 29 30 33 34 36 39 40 43 45 46 48 51 53 54 57 58 1 2 4 7 8 11 13 14 16 19 21 22 25 26 28 31 32 35 37 38 41 42 44 47 49 50 52 55 56 59
That's the convenient way to write it, but the following avoids string processing and is therefore about twice as fast: <lang perl6>sub population-count(Int $n is copy where * >= 0) {
loop (my $c = 0; $n; $n +>= 1) { $c += $n +& 1; } $c;
}</lang>
Python
<lang python>>>> def popcount(n): return bin(n).count("1") ... >>> [popcount(3**i) for i in range(30)] [1, 2, 2, 4, 3, 6, 6, 5, 6, 8, 9, 13, 10, 11, 14, 15, 11, 14, 14, 17, 17, 20, 19, 22, 16, 18, 24, 30, 25, 25] >>> evil, odious, i = [], [], 0 >>> while len(evil) < 30 or len(odious) < 30: ... p = popcount(i) ... if p % 2: odious.append(i) ... else: evil.append(i) ... i += 1 ... >>> evil[:30] [0, 3, 5, 6, 9, 10, 12, 15, 17, 18, 20, 23, 24, 27, 29, 30, 33, 34, 36, 39, 40, 43, 45, 46, 48, 51, 53, 54, 57, 58] >>> odious[:30] [1, 2, 4, 7, 8, 11, 13, 14, 16, 19, 21, 22, 25, 26, 28, 31, 32, 35, 37, 38, 41, 42, 44, 47, 49, 50, 52, 55, 56, 59] >>> </lang>
REXX
<lang rexx>/*REXX program counts the (binary) bits in the binary version of a dec#,*/ /* and also generates a specific number of EVIL and ODIOUS numbers. */ parse arg N B . /*get optional arguments, N and B*/ if N== | N==',' then N=30 /*N given? Then use the default.*/ if B== | B==',' then B= 3 /*B given? Then use the default.*/ numeric digits 3000 /*support most gi-normus numbers.*/ numeric digits max(20,length(B**N)) /*whittle the precision to size. */
/* [↑] a little calc for sizing.*/
$=; do j=0 for N /*generate N popCounts for powers*/
$=$ popCount(B**j) /*get the popCount for a pow of B*/ end /*j*/ /* [↑] append popCount to a list*/ /* [↓] display the pop counts. */
call showList 'powers of' B /*display the list with a header.*/
do j=0 until #==N /*generate N evil numbers. */ if popCount(j)//2 then iterate /*if odd population count, skip.*/ #=#+1 /*bump the evil number counter.*/ $=$ j /*append an evil # to a list.*/ end /*j*/ /* [↑] build a list of evil #s. */ /* [↓] display the evil # list. */
call showList 'evil numbers' /*display the list with a header.*/
do j=0 until #==N /*generate N odious numbers. */ if popCount(j)//2==0 then iterate /*if even population count, skip.*/ #=#+1 /*bump the odious number counter.*/ $=$ j /*append an odious # to a list.*/ end /*j*/ /* [↑] build a list of odious #s*/ /* [↓] display the odious# list.*/
call showList 'odious numbers' /*display the list with a header.*/ exit /*stick a fork in it, we're done.*/ /*──────────────────────────────────D2B subroutine──────────────────────*/ d2b: return word(strip(x2b(d2x(arg(1))),'L',0) 0,1) /*convert dec──►bin*/ /*──────────────────────────────────POPCOUNT subroutine─────────────────*/ popCount: procedure;_=d2b(abs(arg(1))) /*convert the # passed to binary.*/ return length(_)-length(space(translate(_,,1),0)) /*count the one bits.*/ /*──────────────────────────────────SHOWLIST subroutine─────────────────*/ showlist: say; say 'The 1st' N arg(1)':'; say substr($,2); #=0; $=; return</lang> output when using the default input:
The 1st 30 powers of 3: 1 2 2 4 3 6 6 5 6 8 9 13 10 11 14 15 11 14 14 17 17 20 19 22 16 18 24 30 25 25 The 1st 30 evil numbers: 0 3 5 6 9 10 12 15 17 18 20 23 24 27 29 30 33 34 36 39 40 43 45 46 48 51 53 54 57 58 The 1st 30 odious numbers: 1 2 4 7 8 11 13 14 16 19 21 22 25 26 28 31 32 35 37 38 41 42 44 47 49 50 52 55 56 59