Skip to content

Instantly share code, notes, and snippets.

@alex-eg

alex-eg/bitmask.lisp

Created June 2, 2016 21:09
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save alex-eg/506210590736a4c23e87035a07692a3a to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save alex-eg/506210590736a4c23e87035a07692a3a to your computer and use it in GitHub Desktop.
Download ZIP
Raw
bitmask.lisp
(defconstant +debruijn64+ #x22fdd63cc95386d)
(defvar *bit-table*
(let ((a (make-array 64 :element-type '(unsigned-byte 8))))
(loop for i from 0 below 64 do
(setf (aref a (ash (logand #xFFFFFFFFFFFFFFFF
(ash +debruijn64+ i)) -58)) i))
a))
(defun ctz (x)
(declare (type (unsigned-byte 64) x))
(aref *bit-table* (ash (logand #xFFFFFFFFFFFFFFFF
(* +debruijn64+ (logand x (- x)))) -58)))
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment