number of consecutive ones on the left side of an integer using only bit operations

Question

How do I return the number of consecutive ones on the left side of an integer using only bit operations in C (no if, for, while,etc.)? I'm not sure where to begin for this problem.

//BurstSize(-1) = 32, 
//BurstSize(0xFFF0F0F0) = 12
//Legal: ! ~ & ^ | + << >>
//Max ops: 50
int BurstSize(int a) {
   //code 
}

By Left Side, if you mean MSB, then you may fall into trap for negative numbers. — 0xF1, Feb 20 '14 at 06:28
Please explain more by giving some example of your requirement — 0xF1, Feb 20 '14 at 06:29
Is the input a binary number? In other words are we looking for just ones and zeros? — Floris, Feb 20 '14 at 06:29
I believe [Programming Puzzles & Code Golf](http://codegolf.stackexchange.com/) is a better place for this kind of question. — Lee Duhem, Feb 20 '14 at 06:30
@leeduhem : I think OP himself wants an answer. If he wanted to give it as a challenge then it would have been a better place. — 0xF1, Feb 20 '14 at 06:31
no conditinal statements like if and loops to use? only 4 byte integers ? — LearningC, Feb 20 '14 at 06:37
@LưuVĩnhPhúc It is supposed to return the number of significant ones in the binary equivalent of the int — donth2934, Feb 20 '14 at 06:56
Can we assume that the number starts with a 1 (unless the whole number is zero)? Or could you have `0x000000FF` with answer = 8? — Floris, Feb 20 '14 at 07:13

timrau · Accepted Answer · 2014-02-20T06:45:39.470

2

If you use GCC, you could call __builtin_clz() to count leading zeros. Invert the input, then it could be used to count leading ones.

int BurstSize(unsigned a) {
    return __builtin_clz(~a);
}

If you cannot access __builtin_*(), then you can implement the leading zero counting function as in Hacker's Delight:

int nlz4(unsigned x) {
   int y, m, n;

   y = -(x >> 16);      // If left half of x is 0,
   m = (y >> 16) & 16;  // set n = 16.  If left half
   n = 16 - m;          // is nonzero, set n = 0 and
   x = x >> m;          // shift x right 16.
                        // Now x is of the form 0000xxxx.
   y = x - 0x100;       // If positions 8-15 are 0,
   m = (y >> 16) & 8;   // add 8 to n and shift x left 8.
   n = n + m;
   x = x << m;

   y = x - 0x1000;      // If positions 12-15 are 0,
   m = (y >> 16) & 4;   // add 4 to n and shift x left 4.
   n = n + m;
   x = x << m;

   y = x - 0x4000;      // If positions 14-15 are 0,
   m = (y >> 16) & 2;   // add 2 to n and shift x left 2.
   n = n + m;
   x = x << m;

   y = x >> 14;         // Set y = 0, 1, 2, or 3.
   m = y & ~(y >> 1);   // Set m = 0, 1, 2, or 2 resp.
   return n + 2 - m;
}

int BurstSize(unsigned a) {
   return nlz4(~a);
}

edited Feb 20 '14 at 06:45

answered Feb 20 '14 at 06:39

timrau

22,578
4
51
64

2

This sounds like cheating :-) – Lee Duhem Feb 20 '14 at 06:41
@leeduhem Edited my answer so it's not that cheating. – timrau Feb 20 '14 at 06:46
This one is much better. – Lee Duhem Feb 20 '14 at 06:48
Thanks this works for unsigned ints, now I need to try to make it work for signed – donth2934 Feb 20 '14 at 07:01
@donth2934 - don't try to do bit manipulation on signed integers. If you just assign a signed integer to an unsigned variable, things will work. – Floris Feb 20 '14 at 07:09
@timrau - if you follow the question closely, I don't think that subtraction is "allowed". You could circumvent by adding the twos complement, of course. – Floris Feb 20 '14 at 07:17
I modified this by adding the 2's complement of each variable and assigning the parameter to an unsigned int which seems to work – donth2934 Feb 20 '14 at 07:27

score 1 · Answer 2 · edited May 23 '17 at 11:57

Easiest method: invert the number, then find the most significant bit set. The rest you can do yourself (I am 99% sure this is a homework question, so I am giving a hint only. If you really need more help, ask in the comments and I will expand further).

As for finding the most significant bit set, look at https://stackoverflow.com/a/21413883/1967396

for a fairly efficient method.

update Now for a complete method that finds the most significant bit set (after inverting), and then uses a clever lookup table to convert to actual byte (with a modulo 37 trick that didn't come from me... I found it at http://graphics.stanford.edu/~seander/bithacks.html#ZerosOnRightModLookup but made a small change so it works for 32 bits set). I include code to test patterns from 0 to 32 bits - seems to work.

#include <stdio.h>

int burstSize(int n) {
 // return number of consecutive bits set
 unsigned int m, r;
 m = ~n;
 m = m | m >> 1;
 m = m | m >> 2;
 m = m | m >> 4;
 m = m | m >> 8;
 m = m | m >> 16;
 m = ((m ^ (m >> 1)) | 0x80000000) & m;
static const int Mod37BitPosition[] = // map a bit value mod 37 to its position
{
  -1, 0, 1, 26, 2, 23, 27, 0, 3, 16, 24, 30, 28, 11, 0, 13, 4,
  7, 17, 0, 25, 22, 31, 15, 29, 10, 12, 6, 0, 21, 14, 9, 5,
  20, 8, 19, 18
};
r = Mod37BitPosition[m % 37]; // <<<< not sure if this is allowed in your assignment...
return 31 - r; // <<< you could rewrite the LUT so you don't need an operation here. I was lazy.
}

int main(void) {
  printf("%d\n", burstSize(0x00000000));
  printf("%d\n", burstSize(0x80000000));
  printf("%d\n", burstSize(0xC0000000));
  printf("%d\n", burstSize(0xE0000000));
  printf("%d\n", burstSize(0xF0000000));
  printf("%d\n", burstSize(0xF8000000));
  printf("%d\n", burstSize(0xFC000000));
  printf("%d\n", burstSize(0xFE000000));
  printf("%d\n", burstSize(0xFF000000));
  printf("%d\n", burstSize(0xFF800000));
  printf("%d\n", burstSize(0xFFC00000));
  printf("%d\n", burstSize(0xFFE00000));
  printf("%d\n", burstSize(0xFFF00000));
  printf("%d\n", burstSize(0xFFF80000));
  printf("%d\n", burstSize(0xFFFC0000));
  printf("%d\n", burstSize(0xFFFE0000));
  printf("%d\n", burstSize(0xFFFF0000));
  printf("%d\n", burstSize(0xFFFFF800));
  printf("%d\n", burstSize(0xFFFFFC00));
  printf("%d\n", burstSize(0xFFFFFE00));
  printf("%d\n", burstSize(0xFFFFFF00));
  printf("%d\n", burstSize(0xFFFFFFF8));
  printf("%d\n", burstSize(0xFFFFFFFC));
  printf("%d\n", burstSize(0xFFFFFFFE));
  printf("%d\n", burstSize(0xFFFFFFFF));
}

Behnam Safari · Answer 3 · 2014-02-20T06:59:54.890

0

TRY THIS:

unsigned int A=0XFFF0; //your own number
    unsigned int B0=(1 & A)/1;
    unsigned int B1=(2 & A)/2;
    unsigned int B2=(4 & A)/4;
    unsigned int B3=(8 & A)/8;
    unsigned int B4=(16 & A)/16;
    unsigned int B5=(32 & A)/32;
    unsigned int B6=(64 & A)/64;
    unsigned int B7=(128 & A)/128;
    unsigned int B8=(256 & A)/256;
    unsigned int B9=(512 & A)/512;
    unsigned int B10=(1024 & A)/1024;
    unsigned int B11=(2048 & A)/2048;
    unsigned int B12=(4096 & A)/4096;
    unsigned int B13=(8192 & A)/8192;
    unsigned int B14=(16384 & A)/16384;
    unsigned int B15=(32768 & A)/32768;

    int  Result=B15+
                B14*(B15)+
                B13*(B14*B15)+
                B12*(B13*B14*B15)+
                B11*(B12*B13*B14*B15)+
                B10*(B11*B12*B13*B14*B15)+
                B9*(B10*B11*B12*B13*B14*B15)+
                B8*(B9*B10*B11*B12*B13*B14*B15)+
                B7*(B8*B9*B10*B11*B12*B13*B14*B15)+
                B6*(B7*B8*B9*B10*B11*B12*B13*B14*B15)+
                B5*(B6*B7*B8*B9*B10*B11*B12*B13*B14*B15)+
                B4*(B5*B6*B7*B8*B9*B10*B11*B12*B13*B14*B15)+
                B3*(B4*B5*B6*B7*B8*B9*B10*B11*B12*B13*B14*B15)+
                B2*(B3*B4*B5*B6*B7*B8*B9*B10*B11*B12*B13*B14*B15)+
                B1*(B2*B3*B4*B5*B6*B7*B8*B9*B10*B11*B12*B13*B14*B15)+
                B0*(B1*B2*B3*B4*B5*B6*B7*B8*B9*B10*B11*B12*B13*B14*B15);

edited Feb 20 '14 at 06:59

answered Feb 20 '14 at 06:41

Behnam Safari

2,941
6
27
42

Not enough... the input is 32-bit long. – timrau Feb 20 '14 at 06:42
standard C int Type is 16 bit, new compilers made it 32 bit – Behnam Safari Feb 20 '14 at 06:44
1

Question asks for consecutive - this answers for "count all ones" – Floris Feb 20 '14 at 06:51
@Floris I told he can use that idea, so i corrected it! thanks for telling me the issue. – Behnam Safari Feb 20 '14 at 07:01
1

wrong, C doesn't specify anything about size, it just guarantees that int has at least 16 bits. How can a system that have CHAR_BIT = 9, 24 or 32 has 16-bit ints? And those systems are not unexist – phuclv Feb 20 '14 at 07:08
C standard says that "Plain ints have the **natural size** suggested by the architecture of the execution environment (44); the other signed integer types are provided to meet special needs." and clearly 32 bit systems' native size isn't 16 bit – phuclv Feb 20 '14 at 07:10
If you look in the comments, there is a "max ops 50" comment hidden there. This means that although your new solution does count consecutive ones, it will still fail "the assignement". But kudos for trying. – Floris Feb 20 '14 at 07:11
@LưuVĩnhPhúc Yes, Thanks! he need 32 bit int too, but he can use this pattern for 32 bit integer. – Behnam Safari Feb 20 '14 at 07:18

score 0 · Answer 4 · answered Feb 20 '14 at 09:33

The following answer reverses the number to do the operation, it doesn't use the % operator, it uses one - sign though:

#include <iostream>

int burstSize(int n) {
    // Reverse the bits
    n = (n & 0x55555555) <<  1 | (n & 0xAAAAAAAA) >>  1; 
    n = (n & 0x33333333) <<  2 | (n & 0xCCCCCCCC) >>  2; 
    n = (n & 0x0F0F0F0F) <<  4 | (n & 0xF0F0F0F0) >>  4; 
    n = (n & 0x00FF00FF) <<  8 | (n & 0xFF00FF00) >>  8; 
    n = (n & 0x0000FFFF) << 16 | (n & 0xFFFF0000) >> 16; 

    // rightmost 0-bit, produces 0 if none (e.g., 10100111 -> 00001000)
    int r = ~n & (n + 1);

    // r - 1 will give us a mask of the consequtive 1s to isolate (e.g., 0100 -> 0011)
    n = (r - 1) & n;

    // Count the bits  
    n = (n & 0x55555555) + ((n >> 1) & 0x55555555); 
    n = (n & 0x33333333) + ((n >> 2) & 0x33333333); 
    n = (n & 0x0F0F0F0F) + ((n >> 4) & 0x0F0F0F0F); 
    n = (n & 0x00FF00FF) + ((n >> 8) & 0x00FF00FF); 
    n = (n & 0x0000FFFF) + ((n >>16) & 0x0000FFFF);     

    // Return the bit count
    return n;
}

int main() {
    std::cout << burstSize(0x00000000) << std::endl; // 0 
    std::cout << burstSize(0x00010F00) << std::endl; // 0 
    std::cout << burstSize(0x80010F00) << std::endl; // 1     
    std::cout << burstSize(0xF0010F00) << std::endl; // 4
    std::cout << burstSize(0xFFFFFFFE) << std::endl; // 31
    std::cout << burstSize(0xFFFFFFFF) << std::endl; // 32
    return 0;
}

number of consecutive ones on the left side of an integer using only bit operations

4 Answers4