Skip to main content

logcount

logcount Function

Syntax:

logcount integer → number-of-on-bits

Arguments and Values:

integer—an integer .

number-of-on-bits—a non-negative integer .

Description:

Computes and returns the number of bits in the two’s-complement binary representation of integer that are ‘on’ or ‘set’. If integer is negative, the 0 bits are counted; otherwise, the 1 bits are counted.

Examples:

(logcount 0) → 0 
(logcount -1) → 0 
(logcount 7) → 3 

(logcount 13) → 3 ;Two’s-complement binary: ...0001101 
(logcount -13) → 2 ;Two’s-complement binary: ...1110011 
(logcount 30) → 4 ;Two’s-complement binary: ...0011110 
(logcount -30) → 4 ;Two’s-complement binary: ...1100010 
(logcount (expt 2 100)) → 1 
(logcount (- (expt 2 100))) → 100 
(logcount (- (1+ (expt 2 100)))) → 1

Exceptional Situations:

Should signal type-error if its argument is not an integer .

Notes:

Even if the implementation does not represent integers internally in two’s complement binary, logcount behaves as if it did.

The following identity always holds:

(logcount x)

≡ (logcount (- (+ x 1)))

≡ (logcount (lognot x))

Expanded Reference: logcount​

Counting one-bits in non-negative integers​

For non-negative integers, logcount returns the number of 1-bits (popcount).

(logcount 0)
=> 0
(logcount 1)
=> 1
(logcount 7)
=> 3
(logcount 13)
=> 3
(logcount 30)
=> 4

Counting zero-bits in negative integers​

For negative integers, logcount counts the 0-bits in two's-complement representation.

(logcount -1)
=> 0
(logcount -13)
=> 2
(logcount -30)
=> 4

Powers of two​

A power of two has exactly one 1-bit.

(logcount 1)
=> 1
(logcount 1024)
=> 1
(logcount (expt 2 100))
=> 1

Relationship between logcount of n and lognot of n​

logcount of an integer equals logcount of its bitwise complement.

(= (logcount 42) (logcount (lognot 42)))
=> T
(= (logcount 999) (logcount (- (1+ 999))))
=> T

Practical use: checking if a number is a power of two​

A positive integer is a power of two if and only if it has exactly one 1-bit.

(defun power-of-two-p (n)
  (and (plusp n) (= 1 (logcount n))))

(power-of-two-p 16)
=> T
(power-of-two-p 15)
=> NIL
(power-of-two-p 1)
=> T
(power-of-two-p 0)
=> NIL