From 208376ef99da243545efcd6fb02d3469b4c068ed Mon Sep 17 00:00:00 2001
From: Tavian Barnes <tavianator@tavianator.com>
Date: Fri, 10 Nov 2023 12:28:00 -0500
Subject: bit: Implement a branchless has_single_bit()

---
 src/bit.h   | 3 ++-
 tests/bit.c | 3 +++
 2 files changed, 5 insertions(+), 1 deletion(-)

diff --git a/src/bit.h b/src/bit.h
index 21a8076..e680fed 100644
--- a/src/bit.h
+++ b/src/bit.h
@@ -350,7 +350,8 @@ UINT_OVERLOADS(FIRST_TRAILING_ONE)
 
 #define HAS_SINGLE_BIT(type, suffix, width) \
 	static inline bool has_single_bit##suffix(type n) { \
-		return n && !(n & (n - 1)); \
+		/** Branchless n && !(n & (n - 1)) */ \
+		return n < (n ^ (n - 1)) + 1; \
 	}
 
 UINT_OVERLOADS(ROTATE_LEFT)
diff --git a/tests/bit.c b/tests/bit.c
index cb339f4..7b20770 100644
--- a/tests/bit.c
+++ b/tests/bit.c
@@ -117,5 +117,8 @@ int main(void) {
 	verify_eq(bit_floor(0), 0);
 	verify_eq(bit_ceil(0), 1);
 
+	bfs_verify(!has_single_bit(0));
+	bfs_verify(!has_single_bit(UINT32_MAX));
+
 	return EXIT_SUCCESS;
 }
-- 
cgit v1.2.3