Talk:Find first set

Pseudocode verification

In addition to being based closely on the cited sources, I wrote the following C code (requires gcc) to exhaustively verify the given pseudocode in this article over the 32-bit integers:

#include <assert.h>
#include <stdio.h>
#include <strings.h>

int myffs (unsigned int x) {
    if (x == 0) return 0;
    unsigned int t = 1;
    unsigned int r = 1;
    while ((t & x) == 0) {
	t = t << 1;
	r = r + 1;
    }
    return r;
}

#define table_bits 8
int table[1 << table_bits];
int myffs_table (unsigned int x) {
    if (x == 0) return 0;
    unsigned int y = x;
    unsigned int r = 0;
    while (1) {
	if (y & ((1 << table_bits) - 1)) {
	    return r + table[y & ((1 << table_bits) - 1)];
	}
	y = y >> table_bits;
	r = r + table_bits;
    }
    return r;
}

int ctz_debruijn_table[32];
int ctz_debruijn (unsigned int x) {
    return ctz_debruijn_table[((x & (-x)) * 0x077CB531) >> 27];
}

int lg_debruijn_table[32] =
    {0, 9, 1, 10, 13, 21, 2, 29, 11, 14, 16, 18, 22, 25, 3, 30,
     8, 12, 20, 28, 15, 17, 24, 7, 19, 27, 23, 6, 26, 5, 4, 31};
int lg_debruijn (unsigned int x) {
    x = x | (x >> 1); x = x | (x >> 2); x = x | (x >> 4);
    x = x | (x >> 8); x = x | (x >> 16);
    return lg_debruijn_table[(x * 0x07C4ACDDU) >> 27];
}

int myclz(unsigned int x) {
    if (x == 0) return 32;
    int n = 0;
    if ((x & 0xFFFF0000U) == 0) { n += 16; x <<= 16; }
    if ((x & 0xFF000000U) == 0) { n +=  8; x <<=  8; }
    if ((x & 0xF0000000U) == 0) { n +=  4; x <<=  4; }
    if ((x & 0xC0000000U) == 0) { n +=  2; x <<=  2; }
    if ((x & 0x80000000U) == 0) { n +=  1; x <<= 1; }
    return n;
}

int myctz(unsigned int x) {
    if (x == 0) return 32;
    int n = 0;
    if ((x & 0x0000FFFFU) == 0) { n += 16; x >>= 16; }
    if ((x & 0x000000FFU) == 0) { n +=  8; x >>=  8; }
    if ((x & 0x0000000FU) == 0) { n +=  4; x >>=  4; }
    if ((x & 0x00000003U) == 0) { n +=  2; x >>=  2; }
    if ((x & 0x00000001U) == 0) { n +=  1; x >>=  1; }
    return n;
}

int main() {
    unsigned int i;
    for (i=0; i < sizeof(table)/sizeof(*table); i++) table[i] = ffs(i);
    for (i=0; i < 32; i++) ctz_debruijn_table[(0x077CB531U << i) >> 27] = i;

    i = 0;
    do {
	assert(myffs(i) == ffs(i));
	assert(myffs_table(i) == ffs(i));
	if (i != 0) assert(lg_debruijn(i) == 31 - __builtin_clz(i));
	if (i != 0) assert(ctz_debruijn(i) == __builtin_ctz(i));
	assert(myclz(i) == __builtin_clz(i));
	assert(myctz(i) == __builtin_ctz(i));
	i++;
    } while (i != 0);

    return 0;
}

Sorry, looks like a pretty clear WP:SYNTH violation to me. Twin Bird (talk) 09:56, 19 March 2012 (UTC)

I did say in addition to being based closely on the cited sources. This was just to verify I didn't make any small mistakes in interpreting the sources. Dcoetzee 11:28, 19 March 2012 (UTC)

Nearly equivalent?

They're exactly equivalent, surely...? Twin Bird (talk) 09:56, 19 March 2012 (UTC)

Assuming you’re referring to FFS vs CTZ in the second sentence: my guess is it probably depends how you like to number your bits. And the last paragraph in the lead suggests this as well. Perhaps the “nearly equivalent” sentence could be reworded somehow to avoid confusion, without getting too specific? Vadmium (talk, contribs) 11:07, 19 March 2012 (UTC).

That's right. To be fair some sources do use zero-based FFS and some use one-based FFS, so sometimes they're exactly equivalent and sometimes they're just nearly equivalent. I'm not sure how to express this succinctly in the lede. Dcoetzee 11:27, 19 March 2012 (UTC)

VAX instruction

ffs and ffc are VAX instructions, which are where the POSIX functions of the same name came from. 69.54.60.34 (talk) 18:38, 28 March 2012 (UTC)

popc doesn't work for ffs

I've came across this page and noticed this:

 ffs can be computed using:[28]  ffs(x) = pop(x ^ (~(−x)))

This is nonsense. I took the liberty of downloading ref. 28 and it says, on page 231:

 int ffs(zz) /* finds first 1 bit, counting from the LSB */

I believe ffs() is counted from MSB. This is more like fls(), or ctz(). Sorry for not fixing the page myself but I would have to spend hours clarifying the MSB/LSB issues throughout the article, which is something I don't want to do right now.90.183.56.98 (talk) 12:47, 16 July 2013 (UTC)

What's ridiculous? For example, let's use an 8-bit number

x = 0b00110100

-x = 0b11001100;

~-x = 0b00110011, which is the same as x-1;

x^~-x = 0b00000111 and pop(x^~-x) = 3; ffs(0b00110100) counting from the LSB is 3, by Posix rules

Sbalfour (talk) 18:54, 6 November 2019 (UTC)

To answer your other objection, IEEE Std 1003.1-2001 ("POSIX.1") states: "The ffs() function shall find the first bit set (beginning with the least significant bit) in i, and return the index of that bit. Bits are numbered starting at one (the least significant bit)." Are you referring to some other standard? Sbalfour (talk) 19:13, 6 November 2019 (UTC)

CLZ section reads like tutorial

This section is belabored, going from (slow algorithm) to (a little less slower) to (somewhat faster) to (good algorithm). The various approaches should be something like:

• generic bit-by-bit loop - one line of C code serves to illustrate
• binary search, again a few lines of C code suffice (don't need a compilable function)
• binary search + table lookup (which is usually 8-bit, not 4-bit); we don't need separate 8/16/32/64 (128?) bit versions - the encyclopedia is not a tutorial
• convert to floating point and extract exponent
• conditional moves to eliminate branches of binary search
• bit operators AND/OR to eliminate branches of binary search
• deBruijn multiply

The only reason for the generic approach is to illustrate the basics - no one should try to use such a naive algorithm in an actual implementation. The other approaches may all be employed in limited circumstances when a hardware operator isn't available. Sbalfour (talk) 21:59, 5 November 2019 (UTC)

FFS ~= CTZ?

The text says, "nearly equivalent operation is count trailing zeros (ctz)". Nearly equivalent except for what? Sbalfour (talk) 04:14, 6 November 2019 (UTC)

M68000 log2?

The text says: "On platforms with an efficient log2 operation such as M68000..." And exactly what instruction is that? (and substituting M68020 for the possible typo won't fix the problem: M68020 returns for example 3 for log₂(15), but log₂(15)=4 by most people's reckoning). Sbalfour (talk) 04:45, 6 November 2019 (UTC)

Bzzzzt... no!

The text says: "conversely, clz can be computed using ctz by first rounding up to the nearest power of two using shifts and bitwise ORs,". No, it can't actually. That's quite an expensive operation, possibly taking up to 20 machine cycles. We can obviously do anything we need to do by just linearly counting bits in any direction starting from anywhere. There's no arithmetic, logical or bit-wise operation to map trailing zeros to leading zeros, unlike the other direction. Count leading zeros (find high bit) is canonical - there's nothing simple that will convert to it. It must be a hardware operator to be efficient. The paragraph is out of place. Sbalfour (talk) 05:15, 6 November 2019 (UTC)

I'vec reorg'ed this a little, and emphasized that's it's not efficient. Sbalfour (talk) 16:58, 6 November 2019 (UTC)

Software emulation hodge-podge

There's a mixture of code/pseudocode representations, as well as duplication of approaches, considering ffs=ctz+1 (or ffs=ctz for some hardware implementations). We don't need a separate section for ctz. And I'm not sure we need the multiplicity of algorithms presented, or at least not all need to be coded/pseudocoded - it's too much like a tutorial. The unobvious ones like de Bruijn multiplication and floating point conversion, probably need code, but some of the others can be just given a textual description to keep the article concise. Sbalfour (talk) 16:59, 8 November 2019 (UTC)

'w'

ctz4(x): I would assume that 'w' is the width of the word? if so, specify — Preceding unsigned comment added by 75.181.70.150 (talk) 18:40, 22 May 2022 (UTC)

Clz5 is a mix-up?

Correct me, if I'm wrong but what I've noticed is that the clz5 algorithm finds the position of the left-most set bit from the right counting from 0; or in other words clz5(x) = w - clz(x). I came across this realization, while testing that implementation. I have not tried other algorithms, but I suspect there might be a similar issue with others. I'll work on a fix, and will make an edit soon Wisp Valve (talk) 13:35, 1 September 2023 (UTC)

clz3 inhibits the expected behavior, while clz1 clz4 inhibits the same behavior as clz5. It was compared to `__builtin_clz` from GCC.

@Sbalfour, thoughts? Wisp Valve (talk) 14:18, 1 September 2023 (UTC)