Implementing 2D array using BITwise operations

Question

A) int a[][]=new int[20][32];
   a[2][3]=1;
   if(a[2][3]==1)
   {
    System.out.println("true");
   }
B) int a[]=new int[20];
   a[2]=12;
   if ((a[2] & (1 << 3)) != 0)
   {
    System.out.println("true");
   }

In A) I am using 2D int array , I am checking [2,3] is 1 or not
In B) I am using index of Int as 2nd dim. of mat.Here I am checking 3 bit of 2nd element of Array. Which one is better? And why In context of Speed and memory?

I guess he/she missed the "[32];" at the end of line one in the second code — Afshin Moazami
– Afshin Moazami, Commented Oct 2, 2013 at 16:44
The code does not compile and he does forget to add the [32]. I would preffer the B) when you have limited resources, and the A) for execution time. — RamonBoza
– RamonBoza, Commented Oct 2, 2013 at 16:51
I made some changes in the code now It compiles Now can Any one suggest me what is best and Why ? — Tushar
– Tushar, Commented Oct 2, 2013 at 17:20
@AfshinMoazami and Ramon, OP did not forget [32] in the second code. The entire point of B is that the arrays of 32 have been replaced by ints. — user555045
– user555045, Commented Oct 2, 2013 at 17:39

Floris · Accepted Answer · 2013-10-02 17:22:47Z

1

I am going to break my own rule and give an opinion-based "answer".

Clearly your first method is significantly more readable, but it will take more memory. If you are doing this on a very large array, and are constrained in memory, then a bitwise mask makes sense.

I strongly advise you to steer away from "clever" techniques like this unless they are well encapsulated in higher level functions - at which point, for a simple example like this, you will lose the performance benefit (if there even is one) but pick up the memory efficiency.

Of course when the second dimension is not 32, the efficiency gain will be less (and potentially the effort needed to address particular bits skyrockets further).

answered Oct 2, 2013 at 17:22

Floris

46.6k7 gold badges73 silver badges128 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

user555045 · Accepted Answer · 2013-10-02 17:35:31Z

Testing bits may time more time than testing plain ints for small dimensions. For bigger dimensions however, it will become worth it - the second example uses about 32 times less memory (ignoring the overhead of having an array-object), and that means that more of it will stay in caches, which are much faster than main memory (which is very slow compared to a CPU). On today's machines, it is often the case that using more instructions so that you can use the cache better makes things much faster, however, when the entire thing is tiny to begin with, the overhead of testing bits would probably not be worth it.

There is an other case in which using "tiny bit-arrays" like the second example can work out really well: when you can exploit the fact that they're ints instead of just accessing the bits individually. For example, if you intend to do boolean arithmetic on whole 32bit chunks at the time, or if you want to count the number of 1's, or if you want to get the lowest index that has a 1 (especially if you really wanted a mask instead of the index).

Collectives™ on Stack Overflow

Implementing 2D array using BITwise operations

2 Answers 2

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related