popcount.zig (1916B) - Raw
1 //! popcount - population count 2 //! counts the number of 1 bits 3 //! SWAR-Popcount: count bits of duos, aggregate to nibbles, and bytes inside 4 //! x-bit register in parallel to sum up all bytes 5 //! SWAR-Masks and factors can be defined as 2-adic fractions 6 //! TAOCP: Combinational Algorithms, Bitwise Tricks And Techniques, 7 //! subsubsection "Working with the rightmost bits" and "Sideways addition". 8 9 const builtin = @import("builtin"); 10 const std = @import("std"); 11 const common = @import("common.zig"); 12 13 pub const panic = common.panic; 14 15 comptime { 16 @export(&__popcountsi2, .{ .name = "__popcountsi2", .linkage = common.linkage, .visibility = common.visibility }); 17 @export(&__popcountdi2, .{ .name = "__popcountdi2", .linkage = common.linkage, .visibility = common.visibility }); 18 @export(&__popcountti2, .{ .name = "__popcountti2", .linkage = common.linkage, .visibility = common.visibility }); 19 } 20 21 pub fn __popcountsi2(a: i32) callconv(.c) i32 { 22 return popcountXi2(i32, a); 23 } 24 25 pub fn __popcountdi2(a: i64) callconv(.c) i32 { 26 return popcountXi2(i64, a); 27 } 28 29 pub fn __popcountti2(a: i128) callconv(.c) i32 { 30 return popcountXi2(i128, a); 31 } 32 33 inline fn popcountXi2(comptime ST: type, a: ST) i32 { 34 const UT = switch (ST) { 35 i32 => u32, 36 i64 => u64, 37 i128 => u128, 38 else => unreachable, 39 }; 40 var x: UT = @bitCast(a); 41 x -= (x >> 1) & (~@as(UT, 0) / 3); // 0x55...55, aggregate duos 42 x = ((x >> 2) & (~@as(UT, 0) / 5)) // 0x33...33, aggregate nibbles 43 + (x & (~@as(UT, 0) / 5)); 44 x += x >> 4; 45 x &= ~@as(UT, 0) / 17; // 0x0F...0F, aggregate bytes 46 // 8 most significant bits of x + (x<<8) + (x<<16) + .. 47 x *%= ~@as(UT, 0) / 255; // 0x01...01 48 x >>= (@bitSizeOf(ST) - 8); 49 return @intCast(x); 50 } 51 52 test { 53 _ = @import("popcountsi2_test.zig"); 54 _ = @import("popcountdi2_test.zig"); 55 _ = @import("popcountti2_test.zig"); 56 }