bitwise-length, fxlength - bitwise length of an integer

LIBRARY

(import (rnrs))                     ;R6RS
(import (rnrs arithmetic bitwise))  ;R6RS
(import (rnrs arithmetic fixnums))  ;R6RS

SYNOPSIS

(bitwise-length ei)
(fxlength fx)

DESCRIPTION

Returns the number of bits needed to represent ei if it is positive, and the number of bits needed to represent (bitwise-not ei) if it is negative.

The fxlength variant constrains the argument and return value to the fixnum range.

IMPLEMENTATION NOTES

There are no noteworthy differences between implementations of these procedures, apart from performance differences. R6RS gives this standard definition:

(do ((result 0 (+ result 1))
     (bits (if (negative? ei)
               (bitwise-not ei)
               ei)
           (bitwise-arithmetic-shift bits -1)))
    ((zero? bits)
     result))

This implementation runs in O(n) where n is the bitwise length of the input. An implementation which is O(1) is possible if the implementer has access to the internal structure of bignums. Furthermore, CPUs often provide instructions that speed up the fixnum case.

RETURN VALUES

Returns a single exact integer object.

EXAMPLES

(bitwise-length #b1000)
  => 4

(fxlength #xff)
  => 8

(fxlength -1)
  => 0

(fxlength #b-1000)
  => 3

(bitwise-length #x-70)
  => 7

APPLICATION USAGE

This procedure is commonly used to compute the number bytes needed to represent an integer during serialization to an external format.

RATIONALE

This procedure can be implemented more efficiently by the Scheme runtime than by portable code, and it has some use in applications.

COMPATIBILITY

These procedures are specified by R6RS. The generic variant is called integer-length in Common Lisp, SRFI 33, SRFI 60 and SRFI 151.

The usual compatibility concerns surrounding fixnums apply to the fixnum variant.

ERRORS

This procedure can raise exceptions with the following condition types:
&assertion (R6RS)
The wrong number of arguments was passed or an argument was outside its domain.

SEE ALSO

bitwise-first-bit-set(3scm), log(3scm)

STANDARDS

R6RS

HISTORY

MacLisp had an equivalent procedure called haulong.

AUTHORS

This page is part of the scheme-manpages project. It includes materials from the RnRS documents. More information can be found at https://github.com/schemedoc/manpages/.


Markup created by unroff 1.0sc,    March 04, 2023.