[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