CODEWITHSUNDEEP
javaimplementationbit-manipulation
SecureFish
SecureFish

Reputation: 2461

represent an integer using binary in java language

Here is the problem:

You're given 2 32-bit numbers, N & M, and two bit positions, i & j. write a method to set all bits between i and j in N equal to M (e.g. M becomes a substring of N at locating at i and starting at j)

For example: input: int N = 10000000000, M = 10101, i = 2, j = 6; output: int N = 10001010100

My solution:

step 1: compose one mask to clear sets from i to j in N 
 mask=   ( ( ( ((1<<(31-j))-1) << (j-i+1) ) + 1 ) << i  ) - 1 
 for the example, we have 
       mask= 11...10000011
step 2: 
      (N & mask) | (M<<i)

Question: what is the convenient data type to implement the algorithm? for example we have int n = 0x100000 in C, so that we can apply bitwise operators on n. in Java, we have BitSet class, it has clear, set method, but doesnt support left/right shift operator; if we use int, it supports left/right shift, but doesnt have binary representation (I am not talking about binary string representation) what is the best way to implement this?

Code in java (after reading all comments):

int x = Integer.parseInt("10000000000",2);
int x = Integer.parseInt("10101",2);
int i = 2, j = 6;
public static int F(int x, int y, int i, int j){
int mask = (-1<<(j+1)) | (-1>>>(32-i));
return (mask & x ) | (y<<i);   
}

Upvotes: 0

Views: 3691

Answers (3)

user545680
user545680

Reputation:

I think you're misunderstanding how Java works. All values are represented as 'a series of bits' under the hood, ints and longs are included in that.

Based on your question, a rough solution is:

public static int applyBits(int N, int M, int i, int j) {
  M = M << i; // Will truncate left-most bits if too big

  // Assuming j > i
  for(int loopVar = i; loopVar < j; loopVar++) {
    int bitToApply = 1 << loopVar;
    // Set the bit in N to 0
    N = N & ~bitToApply;
    // Apply the bit if M has it set.
    N = (M & bitToApply) | N;
  }

  return N;
}

My assumptions are:

  • i is the right-most (least-significant) bit that is being set in N.
  • M's right-most bit maps to N's ith bit from the right.
  • That premature optimization is the root of all evil - this is O(j-i). If you used a complicated mask like you did in the question you can do it in O(1), but it won't be as readable, and readable code is 97% of the time more important than efficient code.

Upvotes: 0

Paŭlo Ebermann
Paŭlo Ebermann

Reputation: 74750

Java's int has all the operations you need. I did not totally understand your question (too tired now), so I'll not give you a complete answer, just some hints. (I'll revise it later, if needed.)

  • Here are j ones in a row: (1 << j)-1.
  • Here are j ones in a row, followed by i zeros: ((1 << j) - 1) << i.
  • Here is a bitmask which masks out j positions in the middle of x: x & ~(((1 << j) - 1) << i).

Try these with Integer.toBinaryString() to see the results. (They might also give strange results for negative or too big values.)

Upvotes: 0

ratchet freak
ratchet freak

Reputation: 48196

the bit-wise operators |, &, ^ and ~ and the hex literal (0x1010) are all available in java

32 bit numbers are ints if that constraint remains int will be a valid data type

btw

mask = (-1<<j)|(-1>>>(32-i));

is a slightly clearer construction of the mask

Upvotes: 3

Related Questions