Fast'ish bitmap ops (population count, set/clear/toggle bit) in PicoLisp

bitmap64.l

#!/usr/bin/env pil
# 64-bit max
#
# functions to set/clear/toggle a specific bit in an 64-bit integer (8 bytes)

[de lpad (Int)
  (pad 64 (bin Int) ]

[de getbit (Int Pos)
  (& 1 (>> Pos Int) ]

[de setbit (Int Pos)
  (| Int (>> (- Pos) 1) ]

[de clearbit (Int Pos)
  (& Int (- Int (>> (- Pos) 1) ]

[de togglebit (Int Pos)
  (x| Int (>> (- Pos) 1)  ]

[de bitpos (Int Bit) # Bit must be a String, ex: "1" or "0"
  (index Bit (flip (chop (lpad Int) ]

popcount64.l

#!/usr/bin/env pil
# 64-bit max
#
# applies Hamming weight, see: https://en.wikipedia.org/wiki/Hamming_weight#Efficient_implementation

(setq
  k1 (hex "5555555555555555")
  k2 (hex "3333333333333333")
  k4 (hex "0f0f0f0f0f0f0f0f")
  kf (hex "0101010101010101")
  kz (hex "7f") )

[de popcount (Int)
  (let (x (- Int (& k1 (>> 1 Int)))
        y (+ (& x k2) (& k2 (>> 2 x)))
        z (& k4 (+ y (>> 4 y)))
        a (& kz (>> 56 (* kf z))) )
    a ]

(test 6 (popcount 126))
(test 7 (popcount 254))
(test 8 (popcount 255))
(test 15 (popcount (- (** 2 16) 2)))
(test 16 (popcount (- (** 2 16) 1))) # 65535
(test 31 (popcount (- (** 2 32) 2)))
(test 32 (popcount (- (** 2 32) 1))) # 4294967295
(test 63 (popcount (- (** 2 64) 2)))
(test 64 (popcount (- (** 2 64) 1))) # 18446744073709551615

(bye)

uint-bigendian.l

#!/usr/bin/env pil
#
# This function can convert a list of bytes (big-endian) to an unsigned integer
# simplified by http://ix.io/2DwS

(de be-lst-to-uint (Lst)
  (let N 0
      (for B Lst
         (setq N (| B (>> -8 N))) )
      N ) )

# Usage:
# (be-lst-to-uint (128 255)) -> 33023

(test 33023 (be-lst-to-uint (128 255)))
(test 18446744073709551615 (be-lst-to-uint (need 8 255)))

Updated the bitmap64.l to use much more efficient techniques for setting/clearing/toggling bits in a 64-bit integer.

Also updated the popcount64.l to use much more efficient techniques for counting bits in a 64-bit integer.