fastest transition from bitmask to the position of it's lowest SETbit - Unix

This is a discussion on fastest transition from bitmask to the position of it's lowest SETbit - Unix ; Måns Rullgård wrote: > The wikipedia coverage of C related matters is atrocious. Erm - I wasn't checking for C related matters, but rather for 2-complements and binary representation of negative numbers. > Many statements made there are outright lies, ...

+ Reply to Thread
Page 2 of 2 FirstFirst 1 2
Results 21 to 30 of 30

Thread: fastest transition from bitmask to the position of it's lowest SETbit

  1. Re: fastest transition from bitmask to the position of it's lowestSET bit

    Måns Rullgård wrote:
    > The wikipedia coverage of C related matters is atrocious.

    Erm - I wasn't checking for C related matters, but rather for
    2-complements and binary representation of negative numbers.

    > Many statements made there are outright lies, and much of the remainder is
    > inaccurate or incomplete. If you want to learn C programming, get a
    > real book on the subject and a copy of the C99 standard.

    Erm - what exactly makes you think I do not know C++ yet? We weren't
    talking about C++ but rather bitwise operations...

    *confused*

    Lars

  2. Re: fastest transition from bitmask to the position of it's lowestSET bit

    Eric Sosman wrote:
    > I'd suggest you use `unsigned long' rather than plain
    > `long', to avoid problems with negative numbers.

    Good point!

  3. Re: fastest transition from bitmask to the position of it's lowestSET bit

    Eric Sosman wrote:
    >> That way the function doesn't depend on long-aligned values.

    > ... except that it does! If `buf' points to a mis-aligned
    > address, converting it from `void*' to `long*' doesn't magically
    > fix the alignment.


    Okay, I didn't think it would, I just thought when de-referencing the
    pointer, the machine code would maybe read the unaligned long out of the
    2 involved long values and put it into a register, where alignment in
    memory doesn't matter. You know - instead of the 1-cpu-cycle operation
    to store an aligned long at memaddress xy into register z - something
    slightly more cpu-intensive, but not much.

    > I think you're asking to be told how to do X, starting
    > with the assumption that X is impossible ...

    No I didn't start with that assumption, I asked if it was possible due
    to either software emulation specified in a programming language
    standard, or due to hardware emulation by several consecutive simple
    operations. From Måns' reply, I gather that x86-CPUs do exactly this,
    and of course it is slower.

    > The effect of dereferencing an improperly-aligned pointer
    > is undefined; in theory, anything at all could happen.

    Okay, if it's undefined, then I'll use the regular long *

    Thanks!

    Lars

  4. Re: fastest transition from bitmask to the position of it's lowest SET bit

    Lars Uffmann writes:

    > Måns Rullgård wrote:
    >> The wikipedia coverage of C related matters is atrocious.

    > Erm - I wasn't checking for C related matters, but rather for
    > 2-complements and binary representation of negative numbers.
    >
    >> Many statements made there are outright lies, and much of the remainder is
    >> inaccurate or incomplete. If you want to learn C programming, get a
    >> real book on the subject and a copy of the C99 standard.

    > Erm - what exactly makes you think I do not know C++ yet? We weren't
    > talking about C++ but rather bitwise operations...


    I was talking about C, not C++. Bitwise operators are part of the C
    language.

    --
    Måns Rullgård
    mans@mansr.com

  5. Re: fastest transition from bitmask to the position of it's lowest SET bit

    On Fri, 30 May 2008 10:27:42 +0200, Lars Uffmann wrote:
    > Lars Uffmann wrote:
    >> my resulting function now looks like this:
    >>
    >> long extractParam (long *buf, long mask)
    >> {
    >> return (*buf & mask) / (mask & -mask);
    >> }

    >
    > Actually I think I prefer
    >
    > long extractParam (void *buf, long mask)
    > {
    > return (*(long *)buf & mask) / (mask & -mask);
    > }
    >
    > That way the function doesn't depend on long-aligned values. Can
    > someone tell me how a typecast to long* behaves on a
    > non-sizeof(long)-byte-aligned address if the system hardware doesn't
    > support this? Or is it always possible to use non-aligned variables
    > with C compilers if you accept slower processing due to software
    > emulation?


    It may throw a trap. If you try to dereference a pointer that isn't
    propery aligned for `long' in a SPARC system, SIGBUS triggers. IMHO,
    the original is better, as it enforces the alignment constraint that is
    already part of the hardware design in some systems.



  6. Re: fastest transition from bitmask to the position of it's lowestSET bit

    Måns Rullgård wrote:
    > I was talking about C, not C++. Bitwise operators are part of the C
    > language.


    You do realize that you come across as a smartass and nitpicker?

    Seriously man... you're not making much friends with that attitude.

    ....

    Lars

  7. Re: fastest transition from bitmask to the position of it's lowestSET bit

    Giorgos Keramidas wrote:
    > It may throw a trap. If you try to dereference a pointer that isn't
    > propery aligned for `long' in a SPARC system, SIGBUS triggers. IMHO,
    > the original is better, as it enforces the alignment constraint that is
    > already part of the hardware design in some systems.


    Thank you & the others who commented on the alignment thing - I guess
    I'll stick with the old design Just have to make sure I take care of
    extracting parameters that stretch across 2 long values in a different way.

    Best Regards,

    Lars

  8. Re: fastest transition from bitmask to the position of it's lowestSET bit

    Sorry about the delayed reply.

    On May 30, 3:08 am, Lars Uffmann wrote:
    > jason.cipri...@gmail.com wrote:
    > > Also note that if you can guarantee that your mask bits are contiguous

    >
    > Luckily can
    >
    > > and you want to avoid integer division for any reason you can substitute
    > > (M & (~M << 1)) for (M / -M)

    >
    > Erm - I gather that ~M is the 2-complement of M, but then you probably meant
    > (M & (~M + 1)) for (M & -M)


    Yes I totally screwed that up.

    You can substitute (M & (~M << 1)) for (M & -M), but that wouldn't
    gain you anything. There is not a way to avoid the integer division
    there. And there is no M/-M, I am not sure where I pulled that out of
    or what I was talking about. Oops.

    > For your original suggestion doesn't contain M/-M, unless I am just
    > unaware of the binary operator rules and the denominator of V&M/(M&-M)
    > can be picked apart somehow


    No, I assure you it was entirely because I was talking the crazy talk.

    Jason

  9. Re: fastest transition from bitmask to the position of it's lowestSET bit

    On May 30, 12:33 pm, Måns Rullgård wrote:
    > >> The wikipedia coverage of C related matters is atrocious.


    If that's the case then... make it less atrocious! :-)

    > I was talking about C, not C++. Bitwise operators are part of the C
    > language.


    Well, they're part of both languages...

    Jason

  10. Re: fastest transition from bitmask to the position of it's lowestSET bit

    jason.cipriani@gmail.com wrote:
    >> For your original suggestion doesn't contain M/-M, unless I am just
    >> unaware of the binary operator rules and the denominator of V&M/(M&-M)
    >> can be picked apart somehow

    >
    > No, I assure you it was entirely because I was talking the crazy talk.


    Hehe - I'm glad that's cleared up. Your original idea was still a
    perfect solution to my problem

    Best Regards,

    Lars

+ Reply to Thread
Page 2 of 2 FirstFirst 1 2