represent an integer using binary in java language

Question

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);   
}

What do you mean "if we use int... but doesnt have binary representation?" You can absolutely apply & and | to ints in Java. Are you talking about writing an int literal in binary? — Matt Ball
– Matt Ball, Commented Aug 19, 2011 at 0:26
Yes, I am talking about define an int literal in binary which is similar to this statement in C: int N = 0x101010; — SecureFish
– SecureFish, Commented Aug 19, 2011 at 0:38
No binary literals in Java. You've got decimal, octal and hexadecimal. But you could use Integer.parseInt(String s, int radix) with a radix of 2 to start from a String representation. download.oracle.com/javase/6/docs/api/java/lang/… — G_H
– G_H, Commented Aug 19, 2011 at 0:53

ratchet freak · Accepted Answer · 2011-08-19 00:42:38Z

3

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

answered Aug 19, 2011 at 0:42

ratchet freak

48.4k5 gold badges76 silver badges114 bronze badges

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

2 Comments

Paŭlo Ebermann Over a year ago

In Java 7 there even is a binary literal: 0b1010, which might come handy here.

SecureFish Over a year ago

the mask is very nice except that: want to clear the bits between i and j, which is j-i+1 bits. so need -1 << (j+1) | -1 >>> (32-i)

Paŭlo Ebermann · Accepted Answer · 2011-08-19 00:46:52Z

0

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.)

answered Aug 19, 2011 at 0:46

Paŭlo Ebermann

75k20 gold badges150 silver badges217 bronze badges

1 Comment

SecureFish Over a year ago

in this question, we need (j-i+1) positions in the middle of x

score 0 · Accepted Answer · 2011-08-19 04:45:39Z

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.

Collectives™ on Stack Overflow

represent an integer using binary in java language

3 Answers 3

2 Comments

1 Comment

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

2 Comments

1 Comment

Comments

Your Answer

Sign up or log in

Post as a guest

Related