bit manipulation question

Discussion in 'C Programming' started by Elijah Bailey, Dec 3, 2003.

  1. I have a long x;
    I want to write a function

    long f(long x, int k)

    such that it extracts every k-th bit of x, concatenates
    them and returns it. Anyone can help me in writing this
    function?

    examples
    x = 10101010 k = 1 f(x) = 10101010
    x = 10101010 k = 2 f(x) = 1111
    x = 10101010 k = 3 f(x) = 010
    x = 10101010 k = 4 f(x) = 11

    Any bit gurus here who can help me?

    Thanks,
    --Elijah
     
    Elijah Bailey, Dec 3, 2003
    #1
    1. Advertising

  2. Elijah Bailey

    Ben Pfaff Guest

    (Elijah Bailey) writes:

    > I want to write a function
    >
    > long f(long x, int k)
    >
    > such that it extracts every k-th bit of x, concatenates
    > them and returns it. Anyone can help me in writing this
    > function?
    >
    > examples
    > x = 10101010 k = 1 f(x) = 10101010
    > x = 10101010 k = 2 f(x) = 1111
    > x = 10101010 k = 3 f(x) = 010
    > x = 10101010 k = 4 f(x) = 11


    I don't understand your k = 3 example. Shouldn't f(x) = 101 for
    consistency with the others?

    /* I think this'll do the trick, but I haven't tested it or even
    compiled it. In fact, I haven't even tried it out on paper,
    so you'd better think it through carefully before assuming
    anything. */
    unsigned long f(unsigned long x, int k)
    {
    unsigned long out = 0; /* Output so far. */
    unsigned long left = -1; /* Mask of bits left to extract from x. */
    unsigned long msb = ~(left << 1 >> 1); /* Top bit in a unsigned long. */

    do {
    /* Extract MSB of x into LSB of out. */
    out <<= 1;
    if (x & msb)
    out |= 1;

    /* Advance. */
    x <<= k;
    left <<= k;
    } while (left != 0);

    return out;
    }
    --
    int main(void){char p[]="ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz.\
    \n",*q="kl BIcNBFr.NKEzjwCIxNJC";int i=sizeof p/2;char *strchr();int putchar(\
    );while(*q){i+=strchr(p,*q++)-p;if(i>=(int)sizeof p)i-=sizeof p-1;putchar(p\
    );}return 0;}
     
    Ben Pfaff, Dec 3, 2003
    #2
    1. Advertising

  3. Elijah Bailey

    Capstar Guest

    Elijah Bailey wrote:
    > I have a long x;
    > I want to write a function
    >
    > long f(long x, int k)
    >
    > such that it extracts every k-th bit of x, concatenates
    > them and returns it. Anyone can help me in writing this
    > function?
    >
    > examples
    > x = 10101010 k = 1 f(x) = 10101010
    > x = 10101010 k = 2 f(x) = 1111
    > x = 10101010 k = 3 f(x) = 010
    > x = 10101010 k = 4 f(x) = 11
    >
    > Any bit gurus here who can help me?
    >
    > Thanks,
    > --Elijah


    Although this seems to me like a homework asignment, I couldn't resist
    to try something.
    I wouldn't try calling it as you do in your example, because I don't
    think any C compiler would compile it.

    This code is untested and does not take care any special cases. There is
    at least on obvious one, but you can take care of that yourself.

    long f(long x, int k)
    {
    long temp = 0;
    long i, j;

    for(i = 0, j = 0; i < sizeof(x) * 8; i += k, ++j)
    temp |= (x & (1 << i)) >> (i - j);

    return temp;
    }

    Mark
     
    Capstar, Dec 3, 2003
    #3
  4. Elijah Bailey

    Capstar Guest

    Capstar wrote:
    > Elijah Bailey wrote:
    >
    >> I have a long x;
    >> I want to write a function
    >> long f(long x, int k)
    >>
    >> such that it extracts every k-th bit of x, concatenates
    >> them and returns it. Anyone can help me in writing this
    >> function?
    >> examples
    >> x = 10101010 k = 1 f(x) = 10101010
    >> x = 10101010 k = 2 f(x) = 1111
    >> x = 10101010 k = 3 f(x) = 010 x = 10101010 k = 4 f(x) = 11
    >>
    >> Any bit gurus here who can help me?
    >>
    >> Thanks,
    >> --Elijah

    >
    >
    > Although this seems to me like a homework asignment, I couldn't resist
    > to try something.
    > I wouldn't try calling it as you do in your example, because I don't
    > think any C compiler would compile it.
    >
    > This code is untested and does not take care any special cases. There is
    > at least on obvious one, but you can take care of that yourself.
    >
    > long f(long x, int k)
    > {
    > long temp = 0;
    > long i, j;
    >
    > for(i = 0, j = 0; i < sizeof(x) * 8; i += k, ++j)
    > temp |= (x & (1 << i)) >> (i - j);
    >
    > return temp;
    > }
    >
    > Mark
    >


    Hmmm, after reading your post again, I seem to have made a little
    mistake. In my previous post you always start at bit 0. But when you say
    take every k-th bit, you obviously want to start at bit k - 1.

    I also tested it so I'll post my complete test program:
    #include <stdio.h>
    #include <string.h>
    #include <stdlib.h>

    char *bitprint(long x, unsigned long max)
    {
    unsigned long i, j;
    static char bitstring[sizeof(x) * 8 + 1];

    if(max > sizeof(x) * 8) max = sizeof(x) * 8;

    for(i = max - 1, j = 0; j < max; --i, ++j)
    {
    if(x & (1 << i)) bitstring[j] = '1';
    else bitstring[j] = '0';
    }
    bitstring[max] = '\0';

    return bitstring;
    }

    long f(long x, int k)
    {
    long temp = 0;
    unsigned long i, j;

    for(i = k - 1, j = 0; i < sizeof(x) * 8; i += k, ++j)
    temp |= (x & (1 << i)) >> (i - j);

    return temp;
    }

    int main(void)
    {
    long x = 0xaa; /*10101010*/
    int k;
    char *xstring;

    xstring = strdup(bitprint(x, 8));

    for(k = 1; k <= 4; ++k)
    printf("x = %s\tk = %d\t f(x, k) = %s\n", xstring, k, bitprint(f(x,
    k), 8));

    free(xstring);

    return 0;
    }

    Mark

    PS. Isn't strdup in the standard? If I compile this with gcc -W -Wall
    -ansi -pedantic I get: warning: implicit declaration of function `strdup'.
     
    Capstar, Dec 3, 2003
    #4
  5. Elijah Bailey

    nrk Guest

    <snip>

    >
    > PS. Isn't strdup in the standard? If I compile this with gcc -W -Wall
    > -ansi -pedantic I get: warning: implicit declaration of function `strdup'.


    No, strdup is *not* part of the standard.

    <OT>
    According to my manpage, conforms to SYS V R3 and BSD 4.3
    </OT>

    -nrk.
     
    nrk, Dec 3, 2003
    #5
  6. Elijah Bailey

    Mark Gordon Guest

    On Wed, 03 Dec 2003 10:10:04 +0100
    Capstar <> wrote:

    > Capstar wrote:
    > > Elijah Bailey wrote:
    > >
    > >> I have a long x;
    > >> I want to write a function
    > >> long f(long x, int k)
    > >>
    > >> such that it extracts every k-th bit of x, concatenates
    > >> them and returns it. Anyone can help me in writing this
    > >> function?
    > >> examples
    > >> x = 10101010 k = 1 f(x) = 10101010
    > >> x = 10101010 k = 2 f(x) = 1111
    > >> x = 10101010 k = 3 f(x) = 010 x = 10101010 k = 4 f(x) = 11
    > >>
    > >> Any bit gurus here who can help me?
    > >>
    > >> Thanks,
    > >> --Elijah

    > >
    > >
    > > Although this seems to me like a homework asignment, I couldn't
    > > resist to try something.
    > > I wouldn't try calling it as you do in your example, because I don't
    > > think any C compiler would compile it.
    > >
    > > This code is untested and does not take care any special cases.
    > > There is at least on obvious one, but you can take care of that
    > > yourself.
    > >
    > > long f(long x, int k)
    > > {
    > > long temp = 0;
    > > long i, j;
    > >
    > > for(i = 0, j = 0; i < sizeof(x) * 8; i += k, ++j)


    Tut, tut. Assuming CHAR_BIT==8

    > > temp |= (x & (1 << i)) >> (i - j);
    > >
    > > return temp;
    > > }
    > >
    > > Mark
    > >

    >
    > Hmmm, after reading your post again, I seem to have made a little
    > mistake. In my previous post you always start at bit 0. But when you
    > say take every k-th bit, you obviously want to start at bit k - 1.
    >
    > I also tested it so I'll post my complete test program:
    > #include <stdio.h>
    > #include <string.h>
    > #include <stdlib.h>
    >
    > char *bitprint(long x, unsigned long max)


    I would prefer to have the function take a parameter to the buffer
    to be used rather than returning a pointer to a static buffer.

    > {
    > unsigned long i, j;
    > static char bitstring[sizeof(x) * 8 + 1];


    Tut, tut. Still assuming CHAR_BIT==8 throughout this new version.

    > if(max > sizeof(x) * 8) max = sizeof(x) * 8;
    >
    > for(i = max - 1, j = 0; j < max; --i, ++j)
    > {
    > if(x & (1 << i)) bitstring[j] = '1';
    > else bitstring[j] = '0';
    > }
    > bitstring[max] = '\0';
    >
    > return bitstring;
    > }
    >
    > long f(long x, int k)
    > {
    > long temp = 0;
    > unsigned long i, j;
    >
    > for(i = k - 1, j = 0; i < sizeof(x) * 8; i += k, ++j)
    > temp |= (x & (1 << i)) >> (i - j);
    >
    > return temp;
    > }
    >
    > int main(void)
    > {
    > long x = 0xaa; /*10101010*/
    > int k;
    > char *xstring;
    >
    > xstring = strdup(bitprint(x, 8));
    >
    > for(k = 1; k <= 4; ++k)
    > printf("x = %s\tk = %d\t f(x, k) = %s\n", xstring, k,
    > bitprint(f(x,
    > k), 8));
    >
    > free(xstring);
    >
    > return 0;
    > }
    >
    > Mark
    >
    > PS. Isn't strdup in the standard? If I compile this with gcc -W -Wall
    > -ansi -pedantic I get: warning: implicit declaration of function
    > `strdup'.


    No, it's not part of the standard and so when you use -ansi -pedantic it
    is not defined by string.h
    --
    Mark Gordon
    Paid to be a Geek & a Senior Software Developer
    Although my email address says spamtrap, it is real and I read it.
     
    Mark Gordon, Dec 3, 2003
    #6
  7. Elijah Bailey

    Grumble Guest

    Ben Pfaff wrote:
    > Elijah Bailey writes:
    >
    >>I want to write a function
    >>
    >>long f(long x, int k)
    >>
    >>such that it extracts every k-th bit of x, concatenates
    >>them and returns it. Anyone can help me in writing this
    >>function?
    >>
    >>examples
    >> x = 10101010 k = 1 f(x) = 10101010
    >> x = 10101010 k = 2 f(x) = 1111
    >> x = 10101010 k = 3 f(x) = 010
    >> x = 10101010 k = 4 f(x) = 11

    >
    >
    > I don't understand your k = 3 example. Shouldn't f(x) = 101 for
    > consistency with the others?


    Let x_i denote the i_th bit in x counting from right to left.

    In particular, x_0 denotes the right-most bit in x.

    Then f(x)_i = x_{k-1+i*k}

    k=1 => f(x)_i = x_i
    k=2 => f(x)_i = x_{2*i+1}
    k=3 => f(x)_i = x_{3*i+2}

    Thus, from right to left, x_2 | x_5 | x_8
     
    Grumble, Dec 3, 2003
    #7
  8. Elijah Bailey

    nrk Guest

    Elijah Bailey wrote:

    > I have a long x;
    > I want to write a function
    >
    > long f(long x, int k)
    >
    > such that it extracts every k-th bit of x, concatenates
    > them and returns it. Anyone can help me in writing this
    > function?
    >
    > examples
    > x = 10101010 k = 1 f(x) = 10101010
    > x = 10101010 k = 2 f(x) = 1111
    > x = 10101010 k = 3 f(x) = 010
    > x = 10101010 k = 4 f(x) = 11
    >
    > Any bit gurus here who can help me?
    >
    > Thanks,
    > --Elijah


    Probably a bit of beating around the bush going on in the code below, but
    hey, you can verify your function as well :)

    -nrk.

    #include <stdio.h>
    #include <limits.h>
    #include <string.h>

    unsigned long bitextract(unsigned long input, int k) {
    unsigned long ret = 0;
    size_t i;
    int j;

    if ( k <= 1 ) return input;

    for ( i = 0, j = 0; i < sizeof input * CHAR_BIT; i += k, ++j ) {
    input >>= (k-1);
    ret |= (input & 1) << j;
    input >>= 1;
    }

    return ret;
    }

    char *printBinary(char *buf, unsigned long num) {
    static char *hex2bin[] =
    {
    "0000", "0001", "0010", "0011",
    "0100", "0101", "0110", "0111",
    "1000", "1001", "1010", "1011",
    "1100", "1101", "1110", "1111"
    };

    size_t i;

    for ( i = 4; i <= (sizeof num * CHAR_BIT); i += 4 ) {
    int shift = (sizeof num * CHAR_BIT) - i;
    memcpy(buf, hex2bin[((num & (0xFUL << shift)) >> shift)], 4);
    buf += 4;
    }
    *buf = 0;

    return buf - (i - 4);
    }

    int verifyResult(int input, int k, int result) {
    char input_str[sizeof input * CHAR_BIT + 1];
    char result_str[sizeof input * CHAR_BIT + 1];
    char extract_str[sizeof input * CHAR_BIT + 1];
    int i, j;

    printBinary(input_str, input);
    printBinary(result_str, result);

    for ( i = sizeof input_str - 1 - k, j = sizeof extract_str - 2;
    i >= 0;
    i -= k, --j )
    {
    extract_str[j] = input_str;
    }

    while ( j >= 0 ) extract_str[j--] = '0';

    extract_str[sizeof extract_str - 1] = 0;

    return strcmp(result_str, extract_str);
    }

    int main(void) {
    unsigned long input = 0x12345678UL;
    unsigned long result;
    size_t i;

    for ( i = 1; i <= sizeof input * CHAR_BIT; ++i ) {
    result = bitextract(input, i);
    if ( verifyResult(input, i, result) ) {
    printf("Failed for bit %d\n", i);
    break;
    }
    }

    if ( i >= sizeof input * CHAR_BIT )
    printf("Success!\n");

    return 0;
    }
     
    nrk, Dec 3, 2003
    #8
  9. Elijah Bailey

    Capstar Guest

    Mark Gordon wrote:
    > On Wed, 03 Dec 2003 10:10:04 +0100
    > Capstar <> wrote:
    >
    >
    >>Capstar wrote:
    >>
    >>>Elijah Bailey wrote:
    >>>
    >>>
    >>>>I have a long x;
    >>>>I want to write a function
    >>>>long f(long x, int k)
    >>>>
    >>>>such that it extracts every k-th bit of x, concatenates
    >>>>them and returns it. Anyone can help me in writing this
    >>>>function?
    >>>>examples
    >>>> x = 10101010 k = 1 f(x) = 10101010
    >>>> x = 10101010 k = 2 f(x) = 1111
    >>>> x = 10101010 k = 3 f(x) = 010 x = 10101010 k = 4 f(x) = 11
    >>>>
    >>>>Any bit gurus here who can help me?
    >>>>
    >>>>Thanks,
    >>>>--Elijah
    >>>
    >>>
    >>>Although this seems to me like a homework asignment, I couldn't
    >>>resist to try something.
    >>>I wouldn't try calling it as you do in your example, because I don't
    >>>think any C compiler would compile it.
    >>>
    >>>This code is untested and does not take care any special cases.
    >>>There is at least on obvious one, but you can take care of that
    >>>yourself.
    >>>
    >>>long f(long x, int k)
    >>>{
    >>> long temp = 0;
    >>> long i, j;
    >>>
    >>> for(i = 0, j = 0; i < sizeof(x) * 8; i += k, ++j)

    >
    >
    > Tut, tut. Assuming CHAR_BIT==8


    I am not a c.l.c. guru and so I'm not an allmighty know it all. And I
    thought sizeof returned in 8-bit bytes. I'll keep CHAR_BIT in mind next
    time.

    >
    >
    >>> temp |= (x & (1 << i)) >> (i - j);
    >>>
    >>> return temp;
    >>>}
    >>>
    >>>Mark
    >>>

    >>
    >>Hmmm, after reading your post again, I seem to have made a little
    >>mistake. In my previous post you always start at bit 0. But when you
    >>say take every k-th bit, you obviously want to start at bit k - 1.
    >>
    >>I also tested it so I'll post my complete test program:
    >>#include <stdio.h>
    >>#include <string.h>
    >>#include <stdlib.h>
    >>
    >>char *bitprint(long x, unsigned long max)

    >
    >
    > I would prefer to have the function take a parameter to the buffer
    > to be used rather than returning a pointer to a static buffer.


    I don't realy care wat you want. I just needed a function, which would
    return a character array so I could display the value of f(x,k) to
    verify the results easily.

    >
    >
    >>{
    >> unsigned long i, j;
    >> static char bitstring[sizeof(x) * 8 + 1];

    >
    >
    > Tut, tut. Still assuming CHAR_BIT==8 throughout this new version.


    I didn't became an allmighty know it all c.l.c. guru in those 32
    minutes, So I still thought sizeof returned in 8-bit bytes.

    >
    >
    >> if(max > sizeof(x) * 8) max = sizeof(x) * 8;
    >>
    >> for(i = max - 1, j = 0; j < max; --i, ++j)
    >> {
    >> if(x & (1 << i)) bitstring[j] = '1';
    >> else bitstring[j] = '0';
    >> }
    >> bitstring[max] = '\0';
    >>
    >> return bitstring;
    >>}
    >>
    >>long f(long x, int k)
    >>{
    >> long temp = 0;
    >> unsigned long i, j;
    >>
    >> for(i = k - 1, j = 0; i < sizeof(x) * 8; i += k, ++j)
    >> temp |= (x & (1 << i)) >> (i - j);
    >>
    >> return temp;
    >>}
    >>
    >>int main(void)
    >>{
    >> long x = 0xaa; /*10101010*/
    >> int k;
    >> char *xstring;
    >>
    >> xstring = strdup(bitprint(x, 8));
    >>
    >> for(k = 1; k <= 4; ++k)
    >> printf("x = %s\tk = %d\t f(x, k) = %s\n", xstring, k,
    >> bitprint(f(x,
    >>k), 8));
    >>
    >> free(xstring);
    >>
    >> return 0;
    >>}
    >>
    >>Mark
    >>
    >>PS. Isn't strdup in the standard? If I compile this with gcc -W -Wall
    >>-ansi -pedantic I get: warning: implicit declaration of function
    >>`strdup'.

    >
    >
    > No, it's not part of the standard and so when you use -ansi -pedantic it
    > is not defined by string.h


    OK, thanks.
     
    Capstar, Dec 3, 2003
    #9
  10. Elijah Bailey

    Mark Gordon Guest

    On Wed, 03 Dec 2003 17:24:09 +0100
    Capstar <> wrote:

    > Mark Gordon wrote:


    <snip>

    > > Tut, tut. Assuming CHAR_BIT==8

    >
    > I am not a c.l.c. guru and so I'm not an allmighty know it all.


    Nor am I. Perhaps I should not have said "Tut, tut" since it was not my
    intent to cause offence.

    > And I
    > thought sizeof returned in 8-bit bytes. I'll keep CHAR_BIT in mind
    > next time.


    Well, I've been caught out a few times here. One of the good things
    about this group is that people do tend to pick up on the assumptions we
    (and I do deliberately include myself) make.

    <snip>

    > > I would prefer to have the function take a parameter to the buffer
    > > to be used rather than returning a pointer to a static buffer.

    >
    > I don't realy care wat you want. I just needed a function, which would
    > return a character array so I could display the value of f(x,k) to
    > verify the results easily.


    It was merely intended as a helpful stylistic comment, not an
    instruction.

    <snip>

    > > No, it's not part of the standard and so when you use -ansi
    > > -pedantic it is not defined by string.h

    >
    > OK, thanks.


    You're welcome.
    --
    Mark Gordon
    Paid to be a Geek & a Senior Software Developer
    Although my email address says spamtrap, it is real and I read it.
     
    Mark Gordon, Dec 3, 2003
    #10
  11. In article <bqkjp8$8mr$>, Grumble wrote:
    >Ben Pfaff wrote:
    >> Elijah Bailey writes:
    >>
    >>>I want to write a function
    >>>
    >>>long f(long x, int k)
    >>>
    >>>such that it extracts every k-th bit of x, concatenates
    >>>them and returns it. Anyone can help me in writing this
    >>>function?
    >>>
    >>>examples
    >>> x = 10101010 k = 1 f(x) = 10101010
    >>> x = 10101010 k = 2 f(x) = 1111
    >>> x = 10101010 k = 3 f(x) = 010
    >>> x = 10101010 k = 4 f(x) = 11

    >>
    >>
    >> I don't understand your k = 3 example. Shouldn't f(x) = 101 for
    >> consistency with the others?

    >
    >Let x_i denote the i_th bit in x counting from right to left.
    >
    >In particular, x_0 denotes the right-most bit in x.
    >
    >Then f(x)_i = x_{k-1+i*k}
    >
    >k=1 => f(x)_i = x_i
    >k=2 => f(x)_i = x_{2*i+1}
    >k=3 => f(x)_i = x_{3*i+2}
    >
    >Thus, from right to left, x_2 | x_5 | x_8


    Unless I've misunderstood, if x_0 is the
    right-most bit in x, that would make x_8 one to
    the left of the left-most bit in x. For the
    example given, this doesn't exist.

    --
    Michael
     
    Michael Andrew Fyles, Dec 4, 2003
    #11
  12. Elijah Bailey

    Capstar Guest

    Mark Gordon wrote:
    > On Wed, 03 Dec 2003 17:24:09 +0100
    > Capstar <> wrote:
    >
    >
    >>Mark Gordon wrote:

    >
    >
    > <snip>
    >
    >>>Tut, tut. Assuming CHAR_BIT==8

    >>
    >>I am not a c.l.c. guru and so I'm not an allmighty know it all.

    >
    >
    > Nor am I. Perhaps I should not have said "Tut, tut" since it was not my
    > intent to cause offence.
    >


    OK, well then no offence taken. It was indeed the "Tut, tut" that pissed
    me off. I normally don't mind any comment on my code, I even welcome it.

    <snip>
    >
    >>>I would prefer to have the function take a parameter to the buffer
    >>>to be used rather than returning a pointer to a static buffer.

    >>
    >>I don't realy care wat you want. I just needed a function, which would
    >>return a character array so I could display the value of f(x,k) to
    >>verify the results easily.

    >
    >
    > It was merely intended as a helpful stylistic comment, not an
    > instruction.
    >


    I know. Sorry, I normally wouldn't react like that. (Was still pissed).
    But your solution indeed has it's advantages. Mine isn't useable more
    than once in a printf statement for instance. That's why I did:

    xstring = strdup(bitprint(x, 8));

    Mark.
     
    Capstar, Dec 4, 2003
    #12
  13. Elijah Bailey

    Paul Hsieh Guest

    says...
    > I have a long x;
    > I want to write a function
    >
    > long f(long x, int k)
    >
    > such that it extracts every k-th bit of x, concatenates
    > them and returns it. Anyone can help me in writing this
    > function?
    >
    > examples
    > x = 10101010 k = 1 f(x) = 10101010
    > x = 10101010 k = 2 f(x) = 1111
    > x = 10101010 k = 3 f(x) = 010
    > x = 10101010 k = 4 f(x) = 11
    >
    > Any bit gurus here who can help me?


    Its not portable, but I'm sure you can adapt it to your platform of choice:

    long f(long x, int k) {
    switch (k) {
    case 1: return x;
    case 2: x &= 0xAAAAAAAA;
    x = (x | (x >> 1)) & 0x66666666;
    x = (x | (x >> 2)) & 0x1E1E1E1E;
    x = (x | (x >> 4)) & 0x01FE01FE;
    x = (x | (x >> 8)) & 0x0001FFFE;
    return x >> 1;
    case 3: x &= 0x24924924;
    x = (x | (x >> 2)) & 0x0C30C30C;
    x = (x | (x >> 4)) & 0x0C03C03C;
    x = (x | (x >> 8)) & 0x0C0003FC;
    x = (x | (x >> 16)) & 0x00000FFC;
    return x >> 2;
    case 4: x &= 0x88888888;
    x = (x | (x >> 3)) & 0x18181818;
    x = (x | (x >> 6)) & 0x00780078;
    x = (x | (x >> 12)) & 0x000007F8;
    return x >> 3;
    case 5: x &= 0x21084210;
    x = (x | (x >> 4)) & 0x0300C030;
    x = (x | (x >> 8)) & 0x030000F0;
    x = (x | (x >> 16)) & 0x000003F0;
    return x >> 4;
    case 6: x &= 0x20820820;
    x = (x | (x >> 5)) & 0x20060060;
    x = (x | (x >> 10)) & 0x200001E0;
    x = (x | (x >> 20)) & 0x000003E0;
    return x >> 5;
    case 7: x &= 0x08102040;
    x = (x | (x >> 6)) & 0x003000C0;
    x = (x | (x >> 12)) & 0x000003C0;
    return x >> 6;
    case 8: x &= 0x80808080;
    x = (x | (x >> 7)) & 0x01800180;
    x = (x | (x >> 14)) & 0x00000780;
    return x >> 7;
    case 9: x &= 0x04020100;
    x = (x | (x >> 8)) & 0x04000300;
    x = (x | (x >> 16)) & 0x00000700;
    return x >> 8;
    case 10: x &= 0x20080200;
    x = (x | (x >> 9)) & 0x20000600;
    x = (x | (x >> 18)) & 0x00000E00;
    return x >> 9;
    case 11: x &= 0x00200400;
    x = (x | (x >> 10)) & 0x00000C00;
    return x >> 10;
    case 12: x &= 0x00800800;
    x = (x | (x >> 11)) & 0x00001800;
    return x >> 11;
    case 13: x &= 0x02001000;
    x = (x | (x >> 12)) & 0x00003000;
    return x >> 12;
    case 14: x &= 0x08002000;
    x = (x | (x >> 13)) & 0x00006000;
    return x >> 13;
    case 15: x &= 0x20004000;
    x = (x | (x >> 14)) & 0x0000C000;
    return x >> 14;
    case 16: x &= 0x80008000;
    x = (x | (x >> 15)) & 0x00018000;
    return x >> 15;
    case 17: case 18: case 19: case 20: case 21:
    case 22: case 23: case 24: case 25: case 26:
    case 27: case 28: case 29: case 30: case 31:
    case 32: return (x >> (k-1)) & 1;
    default: break;
    }
    return 0;
    }

    --
    Paul Hsieh
    http://www.pobox.com/~qed/
    http://bstring.sf.net/
     
    Paul Hsieh, Dec 5, 2003
    #13
  14. Elijah Bailey

    Grumble Guest

    Michael Andrew Fyles wrote:
    > In article <bqkjp8$8mr$>, Grumble wrote:
    >
    >>Ben Pfaff wrote:
    >>
    >>>Elijah Bailey writes:
    >>>
    >>>
    >>>>I want to write a function
    >>>>
    >>>>long f(long x, int k)
    >>>>
    >>>>such that it extracts every k-th bit of x, concatenates
    >>>>them and returns it. Anyone can help me in writing this
    >>>>function?
    >>>>
    >>>>examples
    >>>>x = 10101010 k = 1 f(x) = 10101010
    >>>>x = 10101010 k = 2 f(x) = 1111
    >>>>x = 10101010 k = 3 f(x) = 010
    >>>>x = 10101010 k = 4 f(x) = 11
    >>>
    >>>
    >>>I don't understand your k = 3 example. Shouldn't f(x) = 101 for
    >>>consistency with the others?

    >>
    >>Let x_i denote the i_th bit in x counting from right to left.
    >>
    >>In particular, x_0 denotes the right-most bit in x.
    >>
    >>Then f(x)_i = x_{k-1+i*k}
    >>
    >>k=1 => f(x)_i = x_i
    >>k=2 => f(x)_i = x_{2*i+1}
    >>k=3 => f(x)_i = x_{3*i+2}
    >>
    >>Thus, from right to left, x_2 | x_5 | x_8

    >
    >
    > Unless I've misunderstood, if x_0 is the
    > right-most bit in x, that would make x_8 one to
    > the left of the left-most bit in x. For the
    > example given, this doesn't exist.


    You are correct.
     
    Grumble, Dec 5, 2003
    #14
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Elijah Bailey

    Bit manipulation question

    Elijah Bailey, Dec 3, 2003, in forum: C++
    Replies:
    4
    Views:
    508
    Naren
    Dec 3, 2003
  2. Replies:
    3
    Views:
    1,802
    Timothy Bendfelt
    Jan 19, 2007
  3. Bartholomew Simpson

    Bit twiddling/manipulation question

    Bartholomew Simpson, Jun 24, 2007, in forum: C Programming
    Replies:
    11
    Views:
    599
    Keith Thompson
    Jun 26, 2007
  4. Replies:
    9
    Views:
    1,011
    Juha Nieminen
    Aug 22, 2007
  5. Jeff.M
    Replies:
    6
    Views:
    186
    Lasse Reichstein Nielsen
    May 4, 2009
Loading...

Share This Page