A week or so ago, I posted a question about what the name of a function
which provided the index to the first low-order 1 bit in an integer. Curiously,
(since Common Lisp defines nearly every other useful function ;-) even Common
Lisp does not have a name for this very useful function.
A finally found a positive reference for the use of the notation v_p(n)
for this function when p=2 -- i.e., v_2(n). This is the so-called p-adic
'valuation' function, which for p=2 is the function I was looking for.
Gouvea, F.Q. p-adic Numbers. Springer, NY 1993.
also
Calderbank, A.R., et al. "A 2-Adic Approach to the Analysis of Cyclic Codes".
Found on a netlib site on the web.
Therefore, I would propose that programming languages now standardize on
such a function and such a name, so that we don't have 10,000 different
names for the same function.
In particular, the name (in the binary case) could be one of:
val2(n)
val_2(n)
valu2(n)
valu_2(n)
valuation2(n)
valuation_2(n)
depending upon whether you belong to the 'long name' (Ada, Lisp, etc.)
school, or the 'short name' (C, etc.) school of function names.
(the "_" here means the ascii "_" character, and not TeX subscript).
Since binary notation is so ubiquitous, I would _not_ suggest generalizing
this function to val(n,2), since val(n,p) for p/=2 is considerably more
expensive to compute, and considerably less common, since val2(n) is useful
for lots of things having nothing to do with p-adic arithmetic.
For the record, here is one not particularly efficient Common Lisp definition
for val2(n):
(defun val2(n) (1- (integer-length (logand n (- n)))))
I'm not sure what the proper value for val2(0) should be, since infinity
is not a usual number available. val2(0) can't be zero, since that doesn't
distinguish from cases like val2(1)=0.
Another question arises as to what the value of val2(floating point number)
should be. I'm open to suggestions.
From: Barry Margolin
Subject: Re: Name for fcn to find first low-order '1' bit in integer
Date:
Message-ID: <5d6291$i2g@tools.bbnplanet.com>
In article <·······················@10.0.2.1>,
Henry Baker <······@netcom.com> wrote:
>A week or so ago, I posted a question about what the name of a function
>which provided the index to the first low-order 1 bit in an integer. Curiously,
>(since Common Lisp defines nearly every other useful function ;-) even Common
>Lisp does not have a name for this very useful function.
Interestingly, I think the PDP-10 has an instruction that computed it (JFFO
-- Jump if Find First One). So it's surprising to me that the MacLisp
developers didn't provide an interface to it; had they done so, it surely
would have been been inherited by Common Lisp.
Or does JFFO count from the high order down, i.e. it's the function used to
compute INTEGER-LENGTH?
>For the record, here is one not particularly efficient Common Lisp definition
>for val2(n):
>(defun val2(n) (1- (integer-length (logand n (- n)))))
Without a built-in, or some low-level interface to bignums, you're probably
not going to do much better than this.
>I'm not sure what the proper value for val2(0) should be, since infinity
>is not a usual number available. val2(0) can't be zero, since that doesn't
>distinguish from cases like val2(1)=0.
Since it's treating the integer as a bit sequence, it probably makes sense
to do what the POSITION function does when it can't find a value in the
sequence: return NIL. Alternatively, you could specificy that this makes
no sense, so it should be undefined (like dividing by 0).
You're the one who needs the function. In your application, what would you
like it to do with 0?
>Another question arises as to what the value of val2(floating point number)
>should be. I'm open to suggestions.
It should probably be undefined (signal TYPE-ERROR under high safety).
This function is clearly intended only for integers.
--
Barry Margolin
BBN Corporation, Cambridge, MA
······@bbnplanet.com
(BBN customers, call (800) 632-7638 option 1 for support)
In article <·······················@10.0.2.1> ······@netcom.com (Henry Baker) writes:
>> >Another question arises as to what the value of val2(floating point number)
>> >should be. I'm open to suggestions.
>>
>> It should probably be undefined (signal TYPE-ERROR under high safety).
>> This function is clearly intended only for integers.
>
>Well, I didn't go into it, but it is my understanding that v_p(n) is defined
>also for _rational_ numbers m/n, and if gcd(m,n)=1, then v_p(m/n)=v_p(m).
>(I hope I got it right; I haven't worked much with p-adics.)
Actually, v_p(m/n) := v_p(m) - v_p(n).
This defines a map v_p: Q -> [-infty, infty), satisfying:
1) v_p(x * y) = v_p(x) + v_p(y),
2) v_p(x + y) <= max(v_p(x), v_p(y)).
The exponential of v_p is analogous to the usual absolute value, except
it's called "non-Archemedian". It defines a topology on Q that's quite
different from the usual topology. (It's called the "p-adic" topology).
We get from Q -> R in the usual way of taking equivalent classes of
Cauchy sequences in Q as elements in R. Similarly here, we can take
Cauchy sequences in this p-adic topology. This process is generally
called "completion". We get Q -> Q_p, "Q_p" is a "p-adic" field. The
valuation v_p naturally extends to Q_p. To take it one step further,
we can form the algebraic closure R -> C in the usual way, and here we
can do the same thing, from Q_p -> Q_p^bar. It turns out that as fields,
C == Q_p^bar for any p, just that they have different absolute values
(and hence topology) on them!
So to answer your question, yes, v_p (or its exponential) can indeed be
extended to all of complex numbers.
--
Zuwei Thomas Feng ······@math.princeton.edu `,`,`,` ,-._;^7 `,`,`,
http://www.math.princeton.edu/~ztfeng `,`,`, < `\ ,`,`,
-=- Check out the Internet MahJong Servers: -=- `,`,`, `-^>__/, ,`,`,
http://www.math.princeton.edu/~ztfeng/mj_servers.html `,`,`,` CHINA ' `,`,`,
From: Elias Martenson
Subject: Re: Name for fcn to find first low-order '1' bit in integer
Date:
Message-ID: <5d85dr$h3t@epimetheus.algonet.se>
In article <··········@tools.bbnplanet.com>, Barry Margolin wrote:
>In article <·······················@10.0.2.1>,
>Henry Baker <······@netcom.com> wrote:
>>A week or so ago, I posted a question about what the name of a function
>>which provided the index to the first low-order 1 bit in an integer. Curiously,
>>(since Common Lisp defines nearly every other useful function ;-) even Common
>>Lisp does not have a name for this very useful function.
>
>Interestingly, I think the PDP-10 has an instruction that computed it (JFFO
>-- Jump if Find First One). So it's surprising to me that the MacLisp
>developers didn't provide an interface to it; had they done so, it surely
>would have been been inherited by Common Lisp.
The Motorola 68020 and upwards have an instruction
called BFFFO (BitField Find First One). So I guess a good name
for such a function would be "ffo".
--
Elias Martenson
·······@algonet.se
From: Frank Brickle
Subject: Re: Name for fcn to find first low-order '1' bit in integer
Date:
Message-ID: <32F7B9A1.5B58@superlink.net>
Elias Martenson wrote:
> The Motorola 68020 and upwards have an instruction
> called BFFFO (BitField Find First One). So I guess a good name
> for such a function would be "ffo".
If I recall, Sun libraries make this available under the name "ffs" (Find First Set [bit]).
From: Elias Martenson
Subject: Re: Name for fcn to find first low-order '1' bit in integer
Date:
Message-ID: <5dauqq$h3f@epimetheus.algonet.se>
In article <·············@superlink.net>, Frank Brickle wrote:
>Elias Martenson wrote:
>
>> The Motorola 68020 and upwards have an instruction
>> called BFFFO (BitField Find First One). So I guess a good name
>> for such a function would be "ffo".
>
>If I recall, Sun libraries make this available under the name "ffs" (Find First Set [bit]).
...and I just nocticed the Linux libc does too. So that would indeed be a
better name.
--
Elias Martenson
·······@algonet.se
From: Tim Hollebeek
Subject: Re: Name for fcn to find first low-order '1' bit in integer
Date:
Message-ID: <5e2it7$q52@cnn.Princeton.EDU>
In article <·············@superlink.net>, Frank Brickle <·······@superlink.net> writes:
> Elias Martenson wrote:
>
> > The Motorola 68020 and upwards have an instruction
> > called BFFFO (BitField Find First One). So I guess a good name
> > for such a function would be "ffo".
>
> If I recall, Sun libraries make this available under the name "ffs" (Find First Set [bit]).
ffs is a BSD-ism, IIRC. You should use it if it is available, since often
it is blindingly fast. Many times it is implemented in terms of an FPU
normalize instruction (e.g. move the raw memory pattern into the FPU,
normalize it, and look at the exponent) which is much faster than any
C code can hope to accomplish the same thing in.
---------------------------------------------------------------------------
Tim Hollebeek | Disclaimer :=> Everything above is a true statement,
Electron Psychologist | for sufficiently false values of true.
Princeton University | email: ···@wfn-shop.princeton.edu
----------------------| http://wfn-shop.princeton.edu/~tim (NEW! IMPROVED!)
From: Henry Baker
Subject: Re: Name for fcn to find first low-order '1' bit in integer
Date:
Message-ID: <hbaker-0302972122000001@10.0.2.1>
In article <··········@tools.bbnplanet.com>, ······@tools.bbnplanet.com
(Barry Margolin) wrote:
> In article <·······················@10.0.2.1>,
> Henry Baker <······@netcom.com> wrote:
> >A week or so ago, I posted a question about what the name of a function
> >which provided the index to the first low-order 1 bit in an integer.
Curiously,
> >(since Common Lisp defines nearly every other useful function ;-) even Common
> >Lisp does not have a name for this very useful function.
>
> Interestingly, I think the PDP-10 has an instruction that computed it (JFFO
> -- Jump if Find First One). So it's surprising to me that the MacLisp
> developers didn't provide an interface to it; had they done so, it surely
> would have been been inherited by Common Lisp.
>
> Or does JFFO count from the high order down, i.e. it's the function used to
> compute INTEGER-LENGTH?
>
> >For the record, here is one not particularly efficient Common Lisp definition
> >for val2(n):
>
> >(defun val2(n) (1- (integer-length (logand n (- n)))))
>
> Without a built-in, or some low-level interface to bignums, you're probably
> not going to do much better than this.
Such a low-level interface to bignums is precisely what I had in mind. Many,
if not most, of such packages already provide such a function for the internal
use of the package itself. I'm suggesting that this function be made available
for users of the package, as well.
> >I'm not sure what the proper value for val2(0) should be, since infinity
> >is not a usual number available. val2(0) can't be zero, since that doesn't
> >distinguish from cases like val2(1)=0.
>
> Since it's treating the integer as a bit sequence, it probably makes sense
> to do what the POSITION function does when it can't find a value in the
> sequence: return NIL. Alternatively, you could specificy that this makes
> no sense, so it should be undefined (like dividing by 0).
>
> You're the one who needs the function. In your application, what would you
> like it to do with 0?
In most of the applications I envision, I won't be calling the function with
an argument of 0. But perhaps other applications that I can't envision
right now, might have a better idea of what this value should be.
> >Another question arises as to what the value of val2(floating point number)
> >should be. I'm open to suggestions.
>
> It should probably be undefined (signal TYPE-ERROR under high safety).
> This function is clearly intended only for integers.
Well, I didn't go into it, but it is my understanding that v_p(n) is defined
also for _rational_ numbers m/n, and if gcd(m,n)=1, then v_p(m/n)=v_p(m).
(I hope I got it right; I haven't worked much with p-adics.)
From: Frank Brickle
Subject: Re: Name for fcn to find first low-order '1' bit in integer
Date:
Message-ID: <32F72EE3.3886@superlink.net>
Henry Baker wrote:
> In most of the applications I envision, I won't be calling the function with
> an argument of 0. But perhaps other applications that I can't envision
> right now, might have a better idea of what this value should be.
0 is a reasonable input when, for example, you're interpreting the input as a
polynomial over GF(2).
From: Bill Schottstaedt
Subject: Re: Name for fcn to find first low-order '1' bit in integer
Date:
Message-ID: <5da4og$bm5@nntp.Stanford.EDU>
> Or does JFFO count from the high order down, i.e. it's the function used
to
> compute INTEGER-LENGTH?
On JFFO: if AC=0, clear A+1, else count "leading zeros" (0s
to the left of the leftmost 1) and place count in A+1.
(Left = high order).
From: Bernie Cosell
Subject: Re: Name for fcn to find first low-order '1' bit in integer
Date:
Message-ID: <32f95854.658268817@news.swva.net>
} In article <··········@tools.bbnplanet.com>, ······@tools.bbnplanet.com
} (Barry Margolin) wrote:
}
} > Interestingly, I think the PDP-10 has an instruction that computed it (JFFO
} > -- Jump if Find First One). So it's surprising to me that the MacLisp
} > developers didn't provide an interface to it; had they done so, it surely
} > would have been been inherited by Common Lisp.
} >
} > Or does JFFO count from the high order down, i.e. it's the function used to
} > compute INTEGER-LENGTH?
JFFO counts from the top down. The reason is that you can find the first
bit in a word in a register from the bottom-up in a single PDP-10
instruction, hence no need for having an extra instruction to do that, but
there's NO way [I know of] to easily find the _highest_order_ set bit of a
word.
/Bernie\
--
Bernie Cosell Fantasy Farm Fibers
······@fantasyfarm.com Pearisburg, VA
--> Too many people, too few sheep <--
If you're talking about fixed-length arithmetic, like C, I found that
it sometimes help to return, not the INDEX of the first bit, but a MASK
containing the first bit. Then
#define LSOB(n) (((~(n))+1)&(n)) /* Least Significant One Bit */
Translation: ~n invert all bits, all lsb 0's are now lsb 1's
+1 all the (now) lsb 1's Carry into the lsb 0
&n only the ms bit that carried is 1 in both sides
For example:
2#101100 n
2#010011 ~n
2#010100 ~n+1
^ The last bit that carried
2#101100 n
2#010100 ~n+1
2#000100 n & ~n+1
So in this usage, LSOB(0) returns 0, namely there is NO 1 bit set.
2#000000 n
2#111111 ~n
2#000000 ~n+1 (Overflows)
? The last bit that carried
2#000000 n
2#000000 ~n+1
2#000000 n & ~n+1
This comes from "Graphic Gems" of some volume (not handy).
It is particularly apt for allocation bitmaps and such, because
1) The mask for removing the bit is already set. (Compared to
n ^= (1UL << FFO(n));
Use n ^= LSOB(n);
2) It doesn't require any "special" instruction set or assembler.
Any computer supporting C already does arithmetic carry.
In article <·······················@10.0.2.1> ······@netcom.com (Henry Baker) writes:
In article <··········@tools.bbnplanet.com>, ······@tools.bbnplanet.com
(Barry Margolin) wrote:
> In article <·······················@10.0.2.1>,
> Henry Baker <······@netcom.com> wrote:
[...]
> -- Jump if Find First One). So it's surprising to me that the MacLisp
> developers didn't provide an interface to it; had they done so, it surely
> would have been been inherited by Common Lisp.
[...]
> >For the record, here is one not particularly efficient Common Lisp definition
> >for val2(n):
>
> >(defun val2(n) (1- (integer-length (logand n (- n)))))
>
> Without a built-in, or some low-level interface to bignums, you're probably
> not going to do much better than this.
Such a low-level interface to bignums is precisely what I had in mind. Many,
if not most, of such packages already provide such a function for the internal
use of the package itself. I'm suggesting that this function be made available
for users of the package, as well.
> >I'm not sure what the proper value for val2(0) should be, since infinity
> >is not a usual number available. val2(0) can't be zero, since that doesn't
> >distinguish from cases like val2(1)=0.
>
> Since it's treating the integer as a bit sequence, it probably makes sense
> to do what the POSITION function does when it can't find a value in the
> sequence: return NIL. Alternatively, you could specificy that this makes
> no sense, so it should be undefined (like dividing by 0).
>
> You're the one who needs the function. In your application, what would you
> like it to do with 0?
In most of the applications I envision, I won't be calling the function with
an argument of 0. But perhaps other applications that I can't envision
right now, might have a better idea of what this value should be.
If it is sufficient to get the *mask*, not the *index*,
you basically can *avoid* deciding the index problem.
So in this usage, LSOB(0) returns 0, namely there is *no* 1 bit set.
> >Another question arises as to what the value of val2(floating point number)
> >should be. I'm open to suggestions.
>
> It should probably be undefined (signal TYPE-ERROR under high safety).
> This function is clearly intended only for integers.
Well, I didn't go into it, but it is my understanding that v_p(n) is defined
also for _rational_ numbers m/n, and if gcd(m,n)=1, then v_p(m/n)=v_p(m).
(I hope I got it right; I haven't worked much with p-adics.)
--
Bernard A. Badger ·······@mail.ccur.com
From: Xcott Craver
Subject: Re: Name for fcn to find first low-order '1' bit in integer
Date:
Message-ID: <5d9ee4$sa9@gannett.math.niu.edu>
Bernard Badger <·······@mail.ccur.com> wrote:
>If you're talking about fixed-length arithmetic, like C, I found that
>it sometimes help to return, not the INDEX of the first bit, but a MASK
>containing the first bit. Then
>#define LSOB(n) (((~(n))+1)&(n)) /* Least Significant One Bit */
>
[...]
>This comes from "Graphic Gems" of some volume (not handy).
Actually, Graphis Gems II mentions a slightly more elegant version:
#define LSOB(n) ((n)&(-n))
See why it works?
,oooooooo8 o ·····@math.niu.edu -- http://www.math.niu.edu/~caj/
o888' `88 ,888. 888
888 ,8'`88. 888 "What he can do with numbers would make a
888o. ,oo ,8oooo88. 888 thousand-dollar-a-night hooker blush like
`888oooo88 o88o o888o 888 a nun."
____________________8o888'______________-Hank Jennings, _Twin_Peaks._ _____
From: Henry Baker
Subject: Re: Name for fcn to find first low-order '1' bit in integer
Date:
Message-ID: <hbaker-0502970736380001@10.0.2.1>
In article <····················@jade.ssd.hcsc.com>, ·······@mail.ccur.com
wrote:
> If you're talking about fixed-length arithmetic, like C, I found that
> it sometimes help to return, not the INDEX of the first bit, but a MASK
> containing the first bit. Then
> #define LSOB(n) (((~(n))+1)&(n)) /* Least Significant One Bit */
Why is this better than
#define TWOS(n) ((-(n))&(n))
??
From: Ken Pizzini
Subject: Re: Name for fcn to find first low-order '1' bit in integer
Date:
Message-ID: <5dho7t$9ts$1@brokaw.wa.com>
In article <·······················@10.0.2.1>,
Henry Baker <······@netcom.com> wrote:
>In article <····················@jade.ssd.hcsc.com>, ·······@mail.ccur.com
>wrote:
>> #define LSOB(n) (((~(n))+1)&(n)) /* Least Significant One Bit */
>
>Why is this better than
>
>#define TWOS(n) ((-(n))&(n))
Because it works for signed n on non-twos-complement machines.
(For unsigned n the C standard forces a twos-complemement
interpretation to -(n).)
On the other hand a compiler is likely to fail to notice the
intended equivalence and issue an extra instruction.
[I trimmed the followups down (and perhaps not aggressivly enough at that);
we seem to be getting C specific here.]
--Ken Pizzini
From: Lawrence Kirby
Subject: Re: Name for fcn to find first low-order '1' bit in integer
Date:
Message-ID: <855149987snz@genesis.demon.co.uk>
In article <····················@jade.ssd.hcsc.com>
·······@mail.ccur.com "Bernard Badger" writes:
>If you're talking about fixed-length arithmetic, like C, I found that
>it sometimes help to return, not the INDEX of the first bit, but a MASK
>containing the first bit. Then
>#define LSOB(n) (((~(n))+1)&(n)) /* Least Significant One Bit */
This is a fairly standard trick, but note that for this to be guaranteed to
work in C n must have type unsigned int or unsigned long. Also it is more
commonly written as:
#define LSOB(n) (-(n) & (n)) /* Least Significant One Bit */
There is also a related trick to clear the least significant one bit:
#define CLEAR_LSOB(n) ((n)-1 & (n)) /* Least Significant One Bit */
--
-----------------------------------------
Lawrence Kirby | ····@genesis.demon.co.uk
Wilts, England | ·········@compuserve.com
-----------------------------------------
From: Jerry Leichter
Subject: Re: Name for fcn to find first low-order '1' bit in integer
Date:
Message-ID: <32F79D23.74DA@smarts.com>
| A week or so ago, I posted a question about what the name of a
| function which provided the index to the first low-order 1 bit in an
| integer. Curiously, (since Common Lisp defines nearly every other
| useful function ;-) even Common Lisp does not have a name for this
| very useful function.
|
| [Neat observation that this is the 2-adic valuation function]
|
| I'm not sure what the proper value for val2(0) should be, since
| infinity is not a usual number available. val2(0) can't be zero,
| since that doesn't distinguish from cases like val2(1)=0.
If you really want this to be the 2-adic valuation function, then the
value has to be infinite, if it's anything. (p-adic valuation functions
are mainly a stepping stone to defining the p-adic norm, given by an
expresion like norm_p(x) = exp(-val(p,x)). These norms act like abso-
lute value. In fact, in an essential sense, "normal" absolute value,
plus norm_p for all primes p, is the set of all "absolute value"
measures on the integers. norm_infinity corresponds to the usual
absolute value. Anyway, for *any* "absolute value", the norm of 0 must
be 0 - which requires the valuation to be infinite.)
| Another question arises as to what the value of val2(floating point
| number) should be. I'm open to suggestions.
In the p-adic theory, the valuation is extended to the rationals by
defining val(a/b) = val(a) - val(b). This gives you a corresponding
absolute value function on the rationals. To go from the rationals to
the reals, we close the rationals, using something like Dedekind cuts.
Doing that requires a notion of absolute value (indirectly, it requires
a metric, but we defined d(a,b) = abs(a-b)). You can go through exactly
the same process using norm_p rather than the usual absolute value. The
resulting field is called the p-adic numbers, and it's very different
from the reals. Of course, abs_p (and val_p) extend to the p-adics, but
they have no meaningful extension I know of to the q-adics (q != p), or
to the reals.
Since FP numbers are all rational anyway, there is an obvious definition
- and in fact val_2 is trivial to compute for a binary FP values. I
don't know what it would be *useful* for, however.
-- Jerry
In article <·············@smarts.com>,
Jerry Leichter <········@smarts.com> wrote:
> A week or so ago, I posted a question about what the name of a
> function which provided the index to the first low-order 1 bit in an
> integer. Curiously, (since Common Lisp defines nearly every other
> useful function ;-) even Common Lisp does not have a name for this
> very useful function.
Several people have pointed out that (n & -n) [or safer (n & (~n+1))]
isolates the lowest bit. However if you require the _index_ that is
only half the job. Converting to an index can be done by finding a modulus
M such that for each single bit number N % M is different and then using
a lookup table to convert the unique value to the appropriate index.
The routines for 16, 32 and 64 bit numbers follow. (I also have
a LISP program to generate the lookup tables.):-
/* Copyright ··········@bifroest.demon.co.uk 1997 */
#include <stdio.h>
typedef unsigned short uint16_t;
#ifndef __alpha
typedef unsigned long uint32_t;
#else
typedef unsigned int uint32_t;
typedef unsigned long uint64_t;
int firstInLongLong(uint64_t value);
#endif
int firstInShort(uint16_t value);
int firstInLong(uint32_t value);
/* All functions return the index of the least significant bit if the
argument
is non-zero and -1 if the argument is zero.
Returning -2 is a programming or hardware error.
*/
int firstInShort(uint16_t value)
{
static const int lookup[19]
= { -1, 0, 1, 13, 2, -2, 14, 6, 3, 8, -2, 12, 15, 5, 7, 11, 4, 10, 9};
return lookup[(value & (~value + 1)) % 19];
}
int firstInLong(uint32_t value)
{
static const int lookup[37]
= { -1, 0, 1, 26, 2, 23, 27, -2, 3, 16, 24, 30, 28, 11, -2, 13, 4, 7,
17, -2, 25, 22, 31, 15, 29, 10, 12, 6, -2, 21, 14, 9, 5, 20, 8, 19,
18};
return lookup[(value & (~value + 1)) % 37];
}
#ifdef __alpha
int firstInLongLong(uint64_t value)
{
static const int lookup[67];
= {-1, 0, 1, 39, 2, 15, 40, 23, 3, 12, 16, 59, 41, 19, 24, 54, 4,
-2, 13, 10, 17, 62, 60, 28, 42, 30, 20, 51, 25, 44, 55, 47, 5,
32, -2, 38, 14, 22, 11, 58, 18, 53, 63, 9, 61, 27, 29, 50, 43,
46, 31, 37, 21, 57, 52, 8, 26, 49, 45, 36, 56, 7, 48, 35, 6, 34, 33};
return lookup[(value & (~value + 1)) % 67];
}
#endif
static void test(int position)
{
unsigned long sample = 1 << position;
int result;
if(position < 16)
{
result = firstInShort((uint16_t)sample);
if(result != position)
printf("sample %d (%x) fails on firstinShort() = %d\n",
position, (uint16_t)sample, result);
}
if(position < 32)
{
result = firstInLong((uint32_t)sample);
if(result != position)
printf("bottom %d (%x) fails on firstinLong() = %d\n",
position, (uint32_t)sample, result);
}
/* Test not written for firstInLongLong as I don't have a 64-bit machine
handy */
}
void main()
{
int index = -1;
printf("Test starting\n");
while (index <32) test(index++);
printf("Test complete\n");
return;
}
··········@bifroest.demon.co.uk FAI-D10204
PGP key 1024/FCE97719 FP: 2A 20 46 10 E5 96 27 40 91 B1 95 BA CA D3 BC 14
Antworten auf Deutsch waeren mir angenehm.
From: Vincent Broman
Subject: Re: Name for fcn to find first low-order '1' bit in integer
Date:
Message-ID: <3jvi85es6t.fsf@Np.nosc.mil>
-----BEGIN PGP SIGNED MESSAGE-----
> a function which provided the index to the first low-order 1 bit in an
> integer
Thanks for the code. Perhaps the function could be called
"factors_of_2_count" or something.
What I have never seen, and would like, already has a usable name:
"floor_log2", but no good implementation for integers that I can come up with.
I.e., I want to be able to find the index of the highest-order one bit in
an integer. (The implementation for floats is nearly trivial, of course. :-)
The only approach I've found is essentially a series of comparisons
that do a binary search for the logarithm base 256, then shift out all
but the top octet and do a direct lookup in a 256-entry table to
get the low-order 8 bits of the result. The search part is unaesthetic, tho.
Any zippier suggestions?
Vincent Broman, code D783 Bayside Email: ······@nosc.mil
Naval Command Control and Ocean Surveillance Center, RDT&E Div.
San Diego, CA 92152-6222, USA Phone: +1 619 553 1641
=== PGP protected mail preferred. For public key finger ······@np.nosc.mil ===
-----BEGIN PGP SIGNATURE-----
Version: 2.6.2
iQCVAwUBMvoalmCU4mTNq7IdAQGj+QP/VWCoha5WxoEYuyHmZLoyDIwow41cIopn
uB4xPzHhYBciYx+yGm71MuMROaQ5IFni+38aMcJOAPFarbrbJPql25N60o1872Ux
z4gnRsnQbLcKS9mHfiM1lkjVbs/T6KpsD3PWgXnDvfwCuLA76DBobZUeIA6xcHh9
xBK6HlSXFZo=
=Uahp
-----END PGP SIGNATURE-----
From: Henry Baker
Subject: Re: Name for fcn to find first low-order '1' bit in integer
Date:
Message-ID: <hbaker-0602972113200001@10.0.2.1>
In article <··············@Np.nosc.mil>, ······@nosc.mil wrote:
> I.e., I want to be able to find the index of the highest-order one bit in
> an integer. (The implementation for floats is nearly trivial, of course. :-)
How about something like ldexp(float(x))?
From: Vincent Broman
Subject: Re: Name for fcn to find first low-order '1' bit in integer
Date:
Message-ID: <3j20asa5my.fsf@Np.nosc.mil>
-----BEGIN PGP SIGNED MESSAGE-----
······@netcom.com suggested:
> How about something like ldexp(float(x))?
If you already have floating point hardware available,
then that's a practical approach.
But the float() call still has to do the search for the highest-order 1 bit,
and it likely does it with some kind of shifting and counting.
Vincent Broman, code D783 Bayside Email: ······@nosc.mil
Naval Command Control and Ocean Surveillance Center, RDT&E Div.
San Diego, CA 92152-6222, USA Phone: +1 619 553 1641
=== PGP protected mail preferred. For public key finger ······@np.nosc.mil ===
-----BEGIN PGP SIGNATURE-----
Version: 2.6.2
iQCVAwUBMvtl5GCU4mTNq7IdAQGXOAP8CFx6UckQ+k3xdaXS9bjFSC05h00kQNdr
yy9Z1GjkqJqtw2m5uJJMgYgK3jzLzC84rogkSxzw4ErgiRGQ/lN/22wvRbRGwTjf
avkYG4CZ2jjwNOXPsIbou3GDDJ4gD6ClQOqCALd1mRr6R8JhvNOV2FlvijPPY1P6
auV+XLtzO4A=
=JDWC
-----END PGP SIGNATURE-----
From: Lawrence Kirby
Subject: Re: Name for fcn to find first low-order '1' bit in integer
Date:
Message-ID: <855520151snz@genesis.demon.co.uk>
In article <··············@Np.nosc.mil> ······@nosc.mil "Vincent Broman" writes:
>-----BEGIN PGP SIGNED MESSAGE-----
>
>······@netcom.com suggested:
>> How about something like ldexp(float(x))?
I'm not quite sure when this is supposed to do, frexp() seems more
appropriate to this thread.
>If you already have floating point hardware available,
>then that's a practical approach.
>But the float() call still has to do the search for the highest-order 1 bit,
>and it likely does it with some kind of shifting and counting.
However this is very simple to implement in constant time in hardware.
--
-----------------------------------------
Lawrence Kirby | ····@genesis.demon.co.uk
Wilts, England | ·········@compuserve.com
-----------------------------------------
On the PowerPC processor at least, there is a very fast way of doing
this in assembler. The algorithm is shown below, the original value is
in x:
t = x - 1
r = NOT x // bit-wise function
s = t AND x // bit-wise function
u = cntlwz (x) // count leading zeros in the word
r = 32 - r // 32 = no. bits in the register
the lowest order bit is of the value - 2^r
For those who can't program in assembler or don't have the cntlwz
function, use the first three instructions to produce a lookup table of
only 32 values or 64 or whatever the register size is. An example it
shown below:
x = 01011000 // 8 bit register
t = x - 1 // t = 01010111
r = NOT x // r = 10100111
s = t AND x // s = 00000111
To then convert s into the first low-order bit, use a table. The results
of the function up till now, the value of s, can be:
01111111
00111111
00011111
00001111
00000111
00000011
00000001
00000000
Have the function compare s with all of these values until a match is
found. The table has to be increased in size for larger registers or
values, but it is very quick and does not require any complicated
floating point functions.
brollo
In article <·············@cableol.co.uk> ······@cableol.co.uk "Brollo" writes:
>For those who can't program in assembler or don't have the cntlwz
>function, use the first three instructions to produce a lookup table of
>only 32 values or 64 or whatever the register size is. An example it
>shown below:
>
>x = 01011000 // 8 bit register
>
>t = x - 1 // t = 01010111
>r = NOT x // r = 10100111
>s = t AND x // s = 00000111
>
>To then convert s into the first low-order bit, use a table. The results
>of the function up till now, the value of s, can be:
>
>01111111
>00111111
>00011111
>00001111
>00000111
>00000011
>00000001
>00000000
>
>Have the function compare s with all of these values until a match is
>found.
If you're going to do a linear scan of a table you might just as well
shift your value right and then count the number of shifts before the
value goes zero. With no memory access this should be significantly faster
on many platforms.
--
-----------------------------------------
Lawrence Kirby | ····@genesis.demon.co.uk
Wilts, England | ·········@compuserve.com
-----------------------------------------
After you do the DUP NEGATE OR, instead of comparing the number with a
series of numbers like 11111000 in a table, you can instead MOD it by a
number slightly larger than the word size, and look up the log. Make
sure that all the possible results of DUP NEGATE OR are different after
n MOD. If you want the bit itself, not its index, of course, you simply
NEGATE.
If you want the highest 1 bit (I wasn't clear which one you wanted), you
do this:
\ 0010010111000011
DUP 1 RSHIFT OR \ 0011011111100011
DUP 2 RSHIFT OR \ 0011111111111011
DUP 4 RSHIFT OR \ 0011111111111111
DUP 8 RSHIFT OR \ 0011111111111111
and proceed as before.
phma
Henry Baker <······@netcom.com> wrote:
> valuation_2(n)
That's ambiguous; ``the valuation at 2 of 8'' could be 3 or 1/8. Better
is the unambiguous notation ord_2.
> Another question arises as to what the value of val2(floating point number)
> should be.
ord_2 (2^e m) = e + ord_2 m. (This interacts very poorly with rounded
arithmetic, since rounding is designed to minimize 0-adic error rather
than 2-adic error.)
---Dan
Put an end to unauthorized mail relaying. http://pobox.com/~djb/qmail.html