Java manipulates large bit numbers

Question

I’m working on the Challenge Street Challenge, changing bits in my free time a little over a week and just spin my wheels at that moment, so I hope someone can give me a pointer or a hint in the right direction.

The task is based on two bit strings A and B and the execution of several queries that manipulate two bit strings.

Let A and B be two N bit numbers. You are given initial values ​​for A and B, and you must write a program that processes three types of queries:

• set_a idx x: set A [idx] to x, where 0 <= idx <N, where A [idx] idx'th least significant bit A.
• set_b idx x: set B [idx] to x, where 0 <= idx <N.
• get_c idx: print C [idx], where C = A + B and 0 <= idx

If the bit numbers are from 1 to 100,000 in length, and the program can have from 1 to 500,000 requests of any set_a, set_b or get_c combination.

To minimize the loop, I use C as a total. When the bit in or B is changed, the changed bit is also added or subtracted from C. Further minimization of the cycle when adding and subtracting is performed from the changed bit to the left hand, while the carry bit is still stored.

private static void add(final boolean[] the_array, final int the_index) { for(int iter = the_array.length - the_index - 1; iter >= 0; iter--) { if(the_array[iter]) { the_array[iter] = false; } else if(!the_array[iter]) { the_array[iter] = true; return ; } } } private static void subtract(final boolean[] the_array, final int the_index) { for(int iter = the_array.length - the_index - 1; iter >= 0; iter--) { if(the_array[iter]) { the_array[iter] = false; return ; } else if(!the_array[iter]) { the_array[iter] = true; } } } 

In general, the program works pretty well, completing the worst edge case with a bit length of 100,000 and 500,000 requests running in about 120 ms, but for the purpose of this task is still not fast enough. Due to the size of the bits, bits quickly exceed the values ​​of primitive integer (long) values ​​in Java, so most of the API is not applicable for this. Since I am not making much progress, increasing the overall amount of startup time begins to suggest that there may be an algorithm or data structure that is better suited for this than just an array. Any suggestions?

Answer 1

Hmm, from the head:
Don't keep C around / updated, just calculate the bit you were asked for on the fly. Remember that when you add the corresponding positions of bits A and B, you only need to look down adjacent less significant bits until you find the point at which they are zero - all that can not carry bits past it. eg.

 A: 001101001010111 B: 010110100010110 ^ asked for C there 1000111^ only need to add bits from here ^ until you get your answer. 

Answer 2

I would use a long [] instead of a logical []. Each long one has 64 bits, and you can perform combined operations such as

 if (the_array[iter] == -1L) // all 1s the_array[iter] = 0L; // all zeros. 

You can perform 64-bit operations at about the same time as the logical operation, making the loop up to 64x faster.

BTW: using boolean[] will use 8 times more memory than long[] , since each boolean uses memory bytes in most JVMs.

---

Examples of using longer types for storing data.

• BitSet uses long[] to store its bits. http://fuseyism.com/classpath/doc/java/util/BitSet-source.html
• BigInteger uses int[] to store its bits. http://developer.classpath.org/doc/java/math/BigInteger-source.html

Depending on what operations you perform, using int may be easier to work with, for example. x = (long) a * b will overflow with long , but not int .

If you scan multiple bits (as BitSet can do), then using long[] can be faster.

---

Adding a benchmark showing the difference in time that it can make.

 public static final int RUNS = 100; public static void main(String... args) throws InterruptedException { boolean[] bools = new boolean[1024 * 1024]; long[] longs = new long[bools.length / 64]; for (int i = 0; i < 5; i++) { testBools(bools); testLongs(longs); } } private static void testBools(boolean[] bools) { long start = System.nanoTime(); for (int t = 0; t < RUNS; t++) { // set all to true for (int i = 0; i < bools.length; i++) bools[i] = true; // search for a false; for (boolean b : bools) if (!b) throw new AssertionError(); // set all to false for (int i = 0; i < bools.length; i++) bools[i] = false; // search for a true; for (boolean b : bools) if (b) throw new AssertionError(); } long time = System.nanoTime() - start; System.out.printf("To set and scan a boolean[] with %,d bits took %,d us%n", bools.length, time / 2/ RUNS / 1000); } private static void testLongs(long[] longs) { long start = System.nanoTime(); for (int t = 0; t < RUNS; t++) { // set all to true for (int i = 0; i < longs.length; i++) longs[i] = ~0; // all 1s // search for a false; for (long l : longs) if (l != ~0) throw new AssertionError(); // set all to false for (int i = 0; i < longs.length; i++) longs[i] = 0; // all 0s // search for a true; for (long l : longs) if (l != 0) throw new AssertionError(); } long time = System.nanoTime() - start; System.out.printf("To set and scan a long[] with %,d bits took %,d us%n", longs.length * Long.SIZE, time / 2/ RUNS / 1000); } 

prints

 To set and scan a boolean[] with 1,048,576 bits took 777 us To set and scan a long[] with 1,048,576 bits took 104 us To set and scan a boolean[] with 1,048,576 bits took 666 us To set and scan a long[] with 1,048,576 bits took 20 us To set and scan a boolean[] with 1,048,576 bits took 537 us To set and scan a long[] with 1,048,576 bits took 18 us To set and scan a boolean[] with 1,048,576 bits took 567 us To set and scan a long[] with 1,048,576 bits took 28 us To set and scan a boolean[] with 1,048,576 bits took 776 us To set and scan a long[] with 1,048,576 bits took 27 us 

In this example, it is about 30 times slower to use a boolean[] compared to a long[]

Answer 3

Похоже, вы уже получили свой первый ответ. Looks like you already got your first answer. На "других способах" привязать событие click, если вы не указали имя класса, существует несколько вариантов. On "other methods", to bind the click event, if you did not specify the class name, there are several options. Вы можете добавить id к тегу и называть его таким образом. You can add id to the tag and call it that way. Или, если вы не хотите добавлять класс или идентификатор, вы можете использовать синтаксис привязки данных со встроенной привязкой "click" для вызова метода на вашей модели представления (очевидно, это не стиль jquery evnet, так что до вас, как вы хотите подключить свои мероприятия). Or, if you do not want to add a class or identifier, you can use the data binding syntax with the built-in "click" binding to call the method on your view model (obviously, this is not the jquery evnet style, so it's up to you how you want to connect your events ) Вот так: Like this:

 Click me 

Answer 4

Вы получаете какие-либо ошибки? Are you getting any errors?

Загрузили ли вы jQuery.js и knockout.js Have you jQuery.js and knockout.js

отправьте код модели просмотра. send view model code.

---

ах! Oh! у вас есть опечатка you have a typo

 $(document).on("click", ".button-delete", function() { // console.log("inside"; <-- here it is console.log("inside"); }); 

DEMO Demo

Answer 5

Наир сначала сообщит мне, что вы хотите сделать здесь если вы хотите удалить кнопку, работает. Nair first tells me what you want to do here if you want to remove the button, it works. затем используйте функцию удаления jquery Ui, и если вы хотите что-то консоль, то просто напишите console.log( "вы хотите консоль" ); then use the jquery Ui delete function, and if you want something console, then just write console.log ("you want a console");

Я думаю, что ваша строка function() { console.log("inside"; }); is wrong I think your line is function() { console.log("inside"; }); is wrong function() { console.log("inside"; }); is wrong . function() { console.log("inside"; }); is wrong .

Answer 6

Я бы рекомендовал вам взглянуть на привязку клика для нокаута, а не на смешивание нокаута со случайным запросом. I would recommend that you take a look at the click binding for a knockout, rather than mixing a knockout with a random request. Связывание кликов позволит вам привязать событие click к функции в модели представления. Linking clicks allows you to bind the click event to a function in the view model.