[Commit] nickle ChangeLog,1.103,1.104 math.5c,1.40,1.41

Bart Massey commit at keithp.com
Tue Nov 30 10:28:24 PST 2004


Committed by: bart

Update of /local/src/CVS/nickle
In directory home.keithp.com:/tmp/cvs-serv26883

Modified Files:
	ChangeLog math.5c 
Log Message:
* math.5c
Added lsb()



Index: ChangeLog
===================================================================
RCS file: /local/src/CVS/nickle/ChangeLog,v
retrieving revision 1.103
retrieving revision 1.104
diff -u -d -r1.103 -r1.104
--- ChangeLog	30 Nov 2004 05:27:53 -0000	1.103
+++ ChangeLog	30 Nov 2004 18:28:21 -0000	1.104
@@ -1,3 +1,8 @@
+2004-11-30  Bart Massey  <bart at cs.pdx.edu>
+
+	* math.5c
+	Added lsb()
+	
 2004-11-29  Keith Packard  <keithp at keithp.com>
 
 	* configure.in:

Index: math.5c
===================================================================
RCS file: /local/src/CVS/nickle/math.5c,v
retrieving revision 1.40
retrieving revision 1.41
diff -u -d -r1.40 -r1.41
--- math.5c	14 Jun 2004 06:43:33 -0000	1.40
+++ math.5c	30 Nov 2004 18:28:21 -0000	1.41
@@ -969,6 +969,47 @@
 	}
 	return below;
     }
+
+    public exception lsb_0();
+
+    public int lsb(int b)
+	/*
+	 * return the bit position of
+	 * the least significant bit of the int argument
+	 * via binary search
+	 */
+    {
+	global bool mask(int b, int ul) {
+	    return (b & ((1 << (ul + 1)) - 1)) != 0;
+	}
+
+	if (b == 0)
+	    raise lsb_0();
+	if (b == -1)
+	    return 0;
+	/* doubling phase */
+	int ul = 1;
+	for (!mask(b, ul); ul *= 2)
+	    /* do nothing */;
+	/* binary search phase */
+	int ll = 0;
+	while (ul > ll + 1) {
+	    int step = (ul - ll) // 2;
+	    if (mask(b, ul - step)) {
+		ul -= step;
+		continue;
+	    }
+	    if (!mask(b, ll + step)) {
+		ll += step;
+		continue;
+	    }
+	    abort("error in binary search");
+	}
+	if (mask(b, ll))
+	    return ll;
+	return ul;
+    }
+
 }
 
 /* XXX these shouldn't be here, but it was *convenient* */




More information about the Commit mailing list