ChessUSA.com TalkChess.com
Hosted by Your Move Chess & Games
 
 FAQFAQ   SearchSearch   MemberlistMemberlist   UsergroupsUsergroups   RegisterRegister 
 ProfileProfile   Log in to check your private messagesLog in to check your private messages   Log inLog in 

Resource for bit twiddlers
Post new topic    TalkChess.com Forum Index -> Computer Chess Club: Programming and Technical Discussions Flat
View previous topic :: View next topic  
Author Message
Gerd Isenberg



Joined: 08 Mar 2006
Posts: 1785
Location: Hattingen, Germany
PostPost subject: Re: Resource for bit twiddlers    Posted: Mon May 28, 2007 12:40 pm Reply to topic Reply with quote
jwes wrote:
I just ran accross this. It is a preprint of part of Knuth's Art of Computer Programming, Vol 4, and covers bit twiddling tricks and techniques.
http://www-cs-faculty.stanford.edu/~knuth/fasc1a.ps.gz


This is really a great ressource - thanks for providing the link.

"tweaking several bytes at once" (page 19), nicely explains some SWAR (SIMD within a regsiter) tricks suggested by H.G. Dietz.

Code:
SWAR add z = x + y 
    z = ((x &~H) + (y &~H)) ^ ((x ^ y) & H)

SWAR sub z = x - y
    z = ((x | H) - (y &~H)) ^ ((x ^~y) & H)

SWAR average z = (x+y)/2 based on x + y = (x^y) + 2*(x&y)
    z = (x & y) + (((x ^ y) & ~L) >> 1)   

For bytewise math, H = 0x8080808080808080 and L = 0x0101010101010101. But one can use arbitrary masks for other sizes such as 6*10 or 5*12 bit as well - or even 64-bit structures with mixed "word"-sizes.

Performing bytewise or rankwise sub using the o ^(o-2r)-trick saves some instructions compared to one Kogge-Stone attack getter, even with general purpose registers:
Code:

u64 eastAttacks(u64 rooks, u64 empty)
{
    empty  = empty &  0xfefefefefefefefe;
    rooks |= empty & (rooks << 1);
    empty  = empty & (empty << 1);
    rooks |= empty & (rooks << 2);
    empty  = empty & (empty << 2);
    rooks |= empty & (rooks << 4);
    return (rooks << 1) & 0xfefefefefefefefe;
}

Code:
u64 eastAttacks(u64 rooks, u64 empty)
{
    const u64 H     = 0x8080808080808080;
    u64 occupied    = rooks | ~empty;
    u64 occNoRook   = rooks ^ occupied;
    u64 difference  = ((occNoRook | H) - (rooks & ~H))
                    ^  (~occupied & H);
    return occupied ^ difference;
}

Gerd
Back to top
View user's profile Send private message
Display posts from previous:   
Subject Author Date/Time
Resource for bit twiddlers J. Wesley Cleveland Fri May 04, 2007 1:55 am
      Re: Resource for bit twiddlers Gerd Isenberg Mon May 28, 2007 12:40 pm
            Re: Resource for bit twiddlers Gerd Isenberg Mon May 28, 2007 3:16 pm
                  Re: Resource for bit twiddlers Gerd Isenberg Mon May 28, 2007 4:35 pm
                        Re: Resource for bit twiddlers Gerd Isenberg Wed May 30, 2007 5:55 pm
                              Re: Resource for bit twiddlers Pradu Kannan Wed May 30, 2007 10:51 pm
                                    Re: Resource for bit twiddlers Gerd Isenberg Thu May 31, 2007 6:17 am
                                          Re: Resource for bit twiddlers Pradu Kannan Fri Jun 01, 2007 12:16 am
                                                Re: Resource for bit twiddlers Gerd Isenberg Fri Jun 01, 2007 8:19 am
            Re: Resource for bit twiddlers Gerd Isenberg Mon Jun 04, 2007 2:58 pm
Post new topic    TalkChess.com Forum Index -> Computer Chess Club: Programming and Technical Discussions

 
Jump to:  
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum




Powered by phpBB © 2001, 2005 phpBB Group
Enhanced with Moby Threads