Thread: Any faster way to access bit maps?

  1. #1
    Registered User
    Join Date
    Dec 2004
    Posts
    163

    Any faster way to access bit maps?

    I have an array declared in integer and each bit of the array represents an item.

    E.g. int Array[2];

    Array is used to represent 64 items.

    So if items 1, 5, 32, 33 exists, the bitmap represented by Array is
    010001000 00000000 00000000 00000001 10000000 00000000 000000000 00000000

    Given Array, I use double for loop to check which items exist

    Code:
     for (i=0; i<2; i++) 
        for (j=0; j<(sizeof(usi)*8); j++) 
          if (Array[i] & (1<<j)) 
           cout << "Item Exist";
    I find that double for loop may not be efficient, do you have more faster way to access the bitmap to check for items?

  2. #2
    aoeuhtns
    Join Date
    Jul 2005
    Posts
    581
    Your double for loop isn't terribly inefficient; the algorithm is still O(n), where n is the number of bits.

    If the bits set to 1 tend to be sparse, you could use a recursive technique -- using divide and conquer. But if they tend to be sparse, you might be better off with a linked list of integers instead.

    When you say "check which items exist", what exactly do you mean? Your code is not actually saving this data for later use.

  3. #3
    Counter-Strike Master
    Join Date
    Dec 2002
    Posts
    38
    what are you trying to access bitmaps for? if you want to copy them or move them around, try using directdraw to access the hardware blitter
    You say "Impressive!", but I already know it
    I'm a hardcore player and I'm not afraid to show it

  4. #4
    Registered User
    Join Date
    Dec 2004
    Posts
    163
    I like the divide and conquer idea, thanks!

    I'm using this bitmap to indicate which items exist in a transaction row of a database. The code I have shown is a part of the algorithm that I am implementing. I had tried using other data structure such as array and linked list for the same purpose and I'm now trying out bitmap.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 7
    Last Post: 12-10-2004, 08:18 AM
  2. Replies: 11
    Last Post: 11-26-2004, 08:13 PM
  3. bit patterns of negtive numbers?
    By chunlee in forum C Programming
    Replies: 4
    Last Post: 11-08-2004, 08:20 AM
  4. faster port access
    By the_head in forum C Programming
    Replies: 5
    Last Post: 10-22-2004, 05:38 PM
  5. 16 bit or 32 bit
    By Juganoo in forum C Programming
    Replies: 9
    Last Post: 12-19-2002, 07:24 AM