1

i have some trouble thinking about how to do a move of ones from a binary in both directions, that means (i will explain with number better)

I have this: 0b10000001 and i want obtain this: 0b01000010 and then 0b00100100 and then 0b00011000.

the sequence what i need to generated is

0b10000001
0b01000010
0b00100100
0b00011000
0b00100100
0b01000010
0b10000001

Somebody can help me? it's possible?

Jaime Andrés Avendaño Villa
  • 13
  • 4
  • 2
    Suppose the number is 0b10100101 — what should the sequence of values be? Presumably 0b01011010 for the next value, but then? What about asymmetric starting values such as 0b10100111? – Jonathan Leffler Apr 12 '18 at 05:11
  • Look up the shift operators << and >>. They shift the bits a given number of places to the left or right. – Mike Apr 12 '18 at 05:16
  • Mike, this operators just shift in one direction, for example if i say 0b10000001 << 1, the result will be 0b00000010, that means, 1 of ones will be lost – Jaime Andrés Avendaño Villa Apr 12 '18 at 05:22
  • what are you trying to accomplish here? what do these values represent? moving bits around just to move them around doesn't seem practical. – Claies Apr 12 '18 at 05:23
  • In theory, you could use a series of XOR operations to get the result you are wanting with the value set you posted. However, this is effectively going to only work if you are using the same values in the same order every single time, and if that's the case, then it doesn't really make sense why you would even need to perform these operations in the first place. – Claies Apr 12 '18 at 05:37
  • 1
    Why not just shift the variable in both directions at the same time, AND them with the bits you want, then OR them? `v = ((v>>1)&0xf0)|((v<<1)&0x0f);` – id01 Apr 12 '18 at 05:52
  • @id0 it is quite implementation dependent, some compiler would carry the integer sign during the bit shift ( if using signed integer ), but you gave most of the answer – dvhh Apr 12 '18 at 05:57
  • And what comes after `0b00011000`? `0b00000000`? – Jabberwocky Apr 12 '18 at 06:13
  • @MichaelWalz well no, must be returned – Jaime Andrés Avendaño Villa Apr 12 '18 at 06:23
  • 1
    @JaimeAndrésAvendañoVilla sorry, but I have no idea what your last comment is supposed to mean. – Jabberwocky Apr 12 '18 at 06:24
  • @MichaelWalz when i tried say "returned" i mean this: final state: 0b00011000 next state: 0b00100100 and continue – Jaime Andrés Avendaño Villa Apr 12 '18 at 07:04
  • @JaimeAndrésAvendañoVilla I suggest you [edit] your question and make clear what _exact_ sequence you want. – Jabberwocky Apr 12 '18 at 07:06

2 Answers2

0

Moving two nibbles (4bit values) left and right in one byte:

uchar x=0b10000001;
uchar l=0b11110000            /*the left nibble*/
uchar r=0b00001111;           /*the right nibble*/
uchar z=((x>>1)&l)|((x<<1)&r) /*the expression for the movement*/
effbiae
  • 1,087
  • 1
  • 7
  • 22
  • 1
    Same remark as I did for @id0, it is quite implementation dependent, char can be signed or unsigned as discussed [here](https://stackoverflow.com/questions/2054939/is-char-signed-or-unsigned-by-default), which mean that the sign might be carried over to fill the blank. – dvhh Apr 12 '18 at 06:16
  • @dvhh the question can be concretely answered in a few lines of code – effbiae Apr 12 '18 at 06:20
  • 1
    Just wanted to point the potential issue if someone uses the code when it used plain `char`, I would explicitly use `unsigned char` to avert ambiguity over the shift operator behavior. – dvhh Apr 12 '18 at 06:29
  • Instead of `uchar`, it is preferible to use the standard `uint8_t` type. – LoPiTaL Apr 12 '18 at 07:13
0

Simplest way to deal with this is to have a static array of the desired values as a look-up table. Use an integer (byte or whatever natural register size) counting from 0 to 6 to index the table. Very fast on modern (or twenty year old) CPUs. Seven values of 8-bit values are easily written by hand.

Bit gymnastics working on the current value to obtain the next with shift operators will run slower, and can't work anyway. You don't have a function for relating one value to the next. For behold:

0b10000001
0b01000010  <-- this value
0b00100100  <-- next value
0b00011000
0b00100100
0b01000010  <-- same value again
0b10000001  <-- different next value!

The same bit pattern appears twice. But the following values are different.

I'm assuming that in real life, you want to do exactly as stated in the question. A lookup table of seven byte values is best.

But if the reality is you (or some future Googler finding this question) are working on, perhaps, 4096-bit long strings of bits, and want to generate a series of bit patterns like shown the question, then even if you want to use a lookup table, some poor sap is going to be stuck writing it. Don't let that be you!

So another more general solution, appying to any size though I'll describe it in terms of the same old 8-bit bytes, in no particular language:

A = 0b10000000
B = 0b00000001
while A nonzero:
    result = A | B
    shift right A, shift left B

Simple and elegant, but you get the value where the two bits meet in the middle twice, 0b00011000. If that's to be avoided, then add code to check for that case and skip ahead to the next iteration.

DarenW
  • 16,549
  • 7
  • 63
  • 102