0
$\begingroup$

My interest is strictly theoretical at this point, but ultimately applied.

  • Is there any problem, theoretically, with defining a byte with m bits, and flipping single bits to connote T/F for a given ordinal value/position?

Essentially I'm looking for the most compact method reading/writing ordinal values in an array that expresses different subsets/combinations of the power set m: P(m) = 2ᵐ.

--------

Purpose: This is related to the game-theoretic conception of Sudoku and Latin Squares. Although our current software is Java based and uses conventional structure and arrays, the ultimate problem size is so large, when we move on to solution checking and integration of neural networks, we're going to have to be optimized. This means flipping the least number of bits, and using the least amount of volume. (We have a custom server allowing cross platform PvP on any device that can has connectivity, and, at some point, bandwidth usage is going to be an issue.)

A. My assumption is writing a single value to a conventional array require more operation or energy than flipping a single bit, even if I have to pull the whole string to flip the bit.

B. If I have to assign a memory address for individual values (1,2,3,4,5,6,7,8) my understanding is each of those addresses reserves an entire byte. By contrast, with a bit array, I only need a single 8-bit byte. [For a neural network, there may be trillions of these arrays, conservatively, without coming close to exhausting the problem space.]

C. If we use conventional arrays vs. bit arrays, the amount of data transferred is significantly greater.

Are there any problems with these assumptions, theoretically speaking?

(Apologies if I've tagged anything incorrectly--feel free to modify :)

|cite|improve this question
$\endgroup$
  • 3
    $\begingroup$ Without the redefinition of byte, this is just a bit array. $\endgroup$ – Yuval Filmus May 11 '18 at 20:25
  • 2
    $\begingroup$ What do you mean by "Is there any problem, theoretically"? What kind of problem? $\endgroup$ – Yuval Filmus May 11 '18 at 20:26
  • $\begingroup$ @YuvalFilmus aah. Thank you for that! (terminology is important--i was reading something recently where someone was talking about "3 bit bytes";) Re: the problem, it's manifold, but arises from the game theoretic conception of Latin Squares and Sudoku. (A basic non-trivial form can be played with here.) In this specific context, because of the problem size, I'm thinking about how to structure a database in the way that flips the least bits (also i don't like excess heat;) Right now I'm working on the mathematical definition, which would relate to this function. $\endgroup$ – DukeZhou May 11 '18 at 21:54
  • 1
    $\begingroup$ Can you ask a more focused question? I don't know how to answer "Is there any problem with creating such-and-such data structure?" That seems too broad to admit a useful answer. The answer is "You can do that if you want". Without telling us what kind of problem you are concerned about, or what would constitute a problem, this seems too open-ended to admit a useful, objective answer. $\endgroup$ – D.W.♦ May 15 '18 at 21:02
  • 1
    $\begingroup$ Coding questions are off-topic here, but you could certainly ask on Stack Overflow. That said, I definitely recommend doing some research/searching first. I suspect there's already lots written about how to implement a bitmap / bit array efficiently. $\endgroup$ – D.W.♦ May 18 '18 at 17:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.