Population count: Difference between revisions
(+ D entry) |
m (tidy up task description) |
||
Line 1: | Line 1: | ||
{{draft task}}[[Category:Mathematics]] |
|||
{{draft task|population count, evil numbers, odious numbers}} |
|||
⚫ | |||
'''population count, evil numbers, odious numbers''' |
|||
⚫ | |||
'''definitions''' |
|||
''[http://mathworld.wolfram.com/EvilNumber.html Evil numbers]'' are non-negative integers that have an even population count; ''[http://mathworld.wolfram.com/OdiousNumber.html odious numbers]'' are positive integers that have an odd population count. |
|||
⚫ | |||
⚫ | |||
⚫ | |||
⚫ | |||
⚫ | |||
::: 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. |
|||
⚫ | |||
⚫ | |||
⚫ | |||
⚫ | |||
⚫ | |||
⚫ | |||
⚫ | |||
⚫ | |||
⚫ | |||
* Sequence [http://oeis.org/A000069 A000069 odious numbers] on The On-Line Encyclopedia of Integer Sequences. |
* Sequence [http://oeis.org/A000069 A000069 odious numbers] on The On-Line Encyclopedia of Integer Sequences. |
||
* Sequence [http://oeis.org/A001969 A001969 evil numbers] on The On-Line Encyclopedia of Integer Sequences. |
* Sequence [http://oeis.org/A001969 A001969 evil numbers] on The On-Line Encyclopedia of Integer Sequences. |
||
* Entry [http://mathworld.wolfram.com/EvilNumber.html evil number] on The Eric Weisstein's World of Mathematics (TM). |
|||
* Entry [http://mathworld.wolfram.com/OdiousNumber.html odious number] on The Eric Weisstein's World of Mathematics (TM). |
|||
* Wiki entry [http://en.wikipedia.org/wiki/Hamming_weight Hamming weight]. |
|||
<br><br> |
|||
=={{header|C}}== |
=={{header|C}}== |
||
Line 330: | Line 316: | ||
/*──────────────────────────────────SHOWLIST subroutine─────────────────*/ |
/*──────────────────────────────────SHOWLIST subroutine─────────────────*/ |
||
showlist: say; say 'The 1st' N arg(1)':'; say substr($,2); #=0; $=; return</lang> |
showlist: say; say 'The 1st' N arg(1)':'; say substr($,2); #=0; $=; return</lang> |
||
'''output''' |
'''output''' when using the default input: |
||
<pre> |
<pre> |
||
The 1st 30 powers of 3: |
The 1st 30 powers of 3: |
Revision as of 12:39, 15 March 2014
The population count (also known as pop count, sideways sum, and Hamming weight) is the number of 1's (ones) in the binary representation of an non-negative integer.
- For example, (which is 101 in binary) has a population count of .
Evil numbers are non-negative integers that have an even population count; odious numbers are positive integers that have an odd population count.
- Task requirements
- write a function (or routine) to return the population count of a non-negative integer.
- all computation of the lists below should start with 0 (zero).
- display the pop count of the 1st thirty powers of ().
- 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.
C
<lang c>#include <stdio.h>
int main() {
{ unsigned long long n = 1; for (int i = 0; i < 30; i++) { // __builtin_popcount() for unsigned int // __builtin_popcountl() for unsigned long // __builtin_popcountll() for unsigned long long printf("%d ", __builtin_popcountll(n)); n *= 3; } printf("\n"); }
int od[30]; int ne = 0, no = 0; printf("evil : "); for (int n = 0; ne+no < 60; n++) { if ((__builtin_popcount(n) & 1) == 0) { if (ne < 30) {
printf("%d ", n); ne++;
} } else { if (no < 30) {
od[no++] = n;
} } } printf("\n"); printf("odious: "); for (int i = 0; i < 30; i++) { printf("%d ", od[i]); } printf("\n");
return 0;
}</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 evil : 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: 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
D
<lang d>void main() {
import std.stdio, std.algorithm, std.range, core.bitop;
const pCount = (ulong n) => popcnt(cast(uint)n) + popcnt(n >> 32); uint.max.iota.map!(i => pCount(3L ^^ i)).take(30).writeln; uint.max.iota.filter!(i => pCount(i) % 2 == 0).take(30).writeln; uint.max.iota.filter!(i => pCount(i) % 2).take(30).writeln;
}</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]
Go
<lang go>package main
import "fmt"
func pop64(w uint64) int {
const ( ff = 1<<64 - 1 mask1 = ff / 3 mask3 = ff / 5 maskf = ff / 17 maskp = maskf >> 3 & maskf ) w -= w >> 1 & mask1 w = w&mask3 + w>>2&mask3 w = (w + w>>4) & maskf return int(w * maskp >> 56)
}
func main() {
n := uint64(1) // 3^0 for i := 0; i < 30; i++ { fmt.Printf("%d ", pop64(n)) n *= 3 } fmt.Println() var od [30]uint64 var ne, no int for n = 0; ne+no < 60; n++ { if pop64(n)&1 == 0 { if ne < 30 { fmt.Printf("%d ", n) ne++ } } else { if no < 30 { od[no] = n no++ } } } fmt.Println() for _, n := range od { fmt.Printf("%d ", n) } fmt.Println()
}</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
Haskell
<lang haskell>import Data.Bits (popCount)
main :: IO () main = do
print $ take 30 $ map popCount $ iterate (* 3) (1 :: Integer) print $ take 30 $ filter (even . popCount) ([0..] :: [Integer]) print $ take 30 $ filter (odd . popCount) ([0..] :: [Integer])</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]
J
Implementation:
<lang J>pcount=: +/"1@#:</lang>
Task:
<lang J> pcount 3^i.30x 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
30{.(#~ 1=2|pcount) i. 100 NB. odd population count
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
30{.(#~ 0=2|pcount) i. 100 NB. even population count
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</lang>
Java
<lang java>import java.math.BigInteger;
public class PopCount {
public static void main(String[] args) {
{ // with int System.out.print("32-bit integer: "); int n = 1; for (int i = 0; i < 20; i++) { System.out.printf("%d ", Integer.bitCount(n)); n *= 3; } System.out.println(); } { // with long System.out.print("64-bit integer: "); long n = 1; for (int i = 0; i < 30; i++) { System.out.printf("%d ", Long.bitCount(n)); n *= 3; } System.out.println(); } { // with BigInteger System.out.print("big integer : "); BigInteger n = BigInteger.ONE; BigInteger three = BigInteger.valueOf(3); for (int i = 0; i < 30; i++) { System.out.printf("%d ", n.bitCount()); n = n.multiply(three); } System.out.println(); }
int[] od = new int[30]; int ne = 0, no = 0; System.out.print("evil : "); for (int n = 0; ne+no < 60; n++) { if ((Integer.bitCount(n) & 1) == 0) { if (ne < 30) { System.out.printf("%d ", n); ne++; } } else { if (no < 30) { od[no++] = n; } } } System.out.println(); System.out.print("odious : "); for (int n : od) { System.out.printf("%d ", n); } System.out.println();
}
}</lang>
- Output:
32-bit integer: 1 2 2 4 3 6 6 5 6 8 9 13 10 11 14 15 11 14 14 17 64-bit integer: 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 big integer : 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 : 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 : 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
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