[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

*To*: srfi-60@xxxxxxxxxxxxxxxxx*Subject*: another operation*From*: sebastian.egner@xxxxxxxxxxx*Date*: Tue, 4 Jan 2005 10:18:14 +0100*Delivered-to*: srfi-60@xxxxxxxxxxxxxxxxx

Hello Aubrey,

Recently, I have been using bit-twiddling extensively for representing and manipulating

subsets of finite sets---one of the purposes you mention in the SRFI document.

Two remarks:

1. As it turns out, I frequently need the following operation missing in SRFI-60:

(FOO x) ==> i ; this is not my proposal for the procedure's name ;-)

i >= 0 is the index of the least significant bit set in integer x in case x > 0,

or in -x-1 if x < 0. If x = 0 then [choose: i = -1 OR (error ...) OR i = #f OR ...]

In other words, i = max {k >= 0 : 2^k divides x} for x > 0.

Note that FOO can be terribly slow when implemented representation-agnostic,

while being lightning fast if the implementor has access to the actual machine words.

2. When scanning different libraries of bit-twiddling, I had stumbled across an implicit

design decision that is worth mentioning because it might swiftly break portability's neck:

"What is the value of (LOGAND)?"

In my application I define (LOGAND) := 0 because the subsets my numbers represent

are finite from way back, their parents are finite, they stay finite and vote finite. However,

(LOGAND) := -1 also makes a lot of sense because -1 (= all bits set) is the neutral element

for bitwise AND---and one can even interpret negative numbers as the complements of

finite sets. (A concept that I later abandonned because the saved case distinctions do

not make up for the confusion this creates.)

Sebastian.

P.S. Just for information, here is the specification of the Bitset (BSET) data type I use.

It turned out to be useful, convenient, and complete for its purpose (which is of course

only one of the potential applications of bit-twiddling):

----

Dr. Sebastian Egner

Senior Scientist

Philips Research Laboratories

Prof. Holstlaan 4 (postbox WY63, kamer WY 6-55)

5656 AA Eindhoven

The Netherlands

tel: +31 40 27-42069

fax: +31 40 27-42566

email: sebastian.egner@xxxxxxxxxxx

**Follow-Ups**:**Re: another operation***From:*Aubrey Jaffer

**Re: another operation***From:*Aubrey Jaffer

**Re: another operation***From:*Aubrey Jaffer

- Prev by Date:
**SRFI 33 vs SLIB** - Next by Date:
**SRFI-33 vs SLIB** - Previous by thread:
**Re: SRFI 33 vs SLIB** - Next by thread:
**Re: another operation** - Index(es):