Count the number of set bits in an integer

Resources Community Resources
1

I’ll add more detail, implementations of bit counting in Luau, and comparisons later. I just couldn’t find a hypothetical function like bit32.count_bits and was kinda bored lol so here you go

local Kernighan = function(n)
	local count = 0

	while n > 0 do
		n = bit32.band(n, n - 1)
		count += 1
	end

	return count
end

Here’s a Luau implementation of Brian Kernighan’s algorithm for counting the number of set bits, or the number of 1s, in the bit representation of an integer.

2 Likes
2

I just found out that something else similar to this on the DevForum exists

I’ll be updating this topic with things I find regarding counting bits though

1 Like
3

This is an interesting topic to release a resource on!!
I want to add the “Nifty Parallel Count” on this stackoverflow post.

A super fun algorithm! A lot to learn here…

local function popcnt32(n: number)
	n = bit32.band(n, 0x55555555) + bit32.band(bit32.rshift(n,  1), 0x55555555)
	n = bit32.band(n, 0x33333333) + bit32.band(bit32.rshift(n,  2), 0x33333333)
	n = bit32.band(n, 0x0f0f0f0f) + bit32.band(bit32.rshift(n,  4), 0x0f0f0f0f)
	n = bit32.band(n, 0x00ff00ff) + bit32.band(bit32.rshift(n,  8), 0x00ff00ff)
	n = bit32.band(n, 0x0000ffff) + bit32.band(bit32.rshift(n, 16), 0x0000ffff)
	return n
end
2 Likes