Decoding a message hidden in a picture (C++);

[79wjd]

I have to decode a message, which is hidden in a picture. The message is stored in the least significant bit of green. So every 8 pixels is a new character. And the message is terminated by a NULL character. Here's the code I have now, but every "character" prints as '255' for some reason and I'm not sure why.

P.s. when I run the print statement to print the LSB's, they're not all 1's, but every character in that same print statement is a 1. So I'm doing something wrong when I'm trying to combine all the LSBs together into the 'character'.

[Mr_KoKa]

First what i came up with is that you don't clear character so if it was 00001111 before at then you will do 00001111  | 0 it wont turn into 00001110

second thing, you add character to message after loop through whole image, I think you should do message += character after you gather all 8 bits (where you check if its is null bit would be appropriate).

 

I still don't know if you do all other bit move correctly, but those are the main issues, but I may be wrong - i just guess, you can correct me if I'm wrong.

[79wjd]

First what i came up with is that you don't clear character so if it was 00001111 before at then you will do 00001111  | 0 it wont turn into 00001110

second thing, you add character to message after loop through whole image, I think you should do message += character after you gather all 8 bits (where you check if its is null bit would be appropriate).

 

I still don't know if you do all other bit move correctly, but those are the main issues, but I may be wrong - i just guess, you can correct me if I'm wrong.

Okay, I feel stupid. I caught the message+= thing, but didn't think about clearing the character...whoops.

[Mr_KoKa]

Okay, I feel stupid. I caught the message+= thing, but didn't think about clearing the character...whoops.

 

Yup, if you forgot to do it when reading you most likely forgot it when writing too. When you inserting message to BMP file, you need to clear lsb of green byte first and then overwrite it by new byte so when it was 1 it can be 0.

 

I just made similar app so I can be sure what I am talking about.

[79wjd]

Yup, if you forgot to do it when reading you most likely forgot it when writing too. When you inserting message to BMP file, you need to clear lsb of green byte first and then overwrite it by new byte so when it was 1 it can be 0.

 

I just made similar app so I can be sure what I am talking about.

I just have to decode the message from the picture. So no need to worry about that

On a related note, I have to count the number of ones in an unsigned 32 bit integer, but I have to do it in O(logn) time. I was thinking doing it recursively, but I'm not really sure how to (since I can only pass in the input as an argument).

[Mr_KoKa]

I forgot already how O notation works but, what I remember is that if you want to check if something isn't or is there, you need to check it, so if you have 32 bit integer, you will do at least (and exactly) 32 checks so this would be O(n)? and I don't think if you can do it O(logn), if the task would be find if there is any 1, then yes, binary search would do.

 

But as always I may be wrong (I hate this but, yeah, I am never sure).

[79wjd]

I forgot already how O notation works but, what I remember is that if you want to check if something isn't or is there, you need to check it, so if you have 32 bit integer, you will do at least (and exactly) 32 checks so this would be O(n)? and I don't think if you can do it O(logn), if the task would be find if there is any 1, then yes, binary search would do.

 

But as always I may be wrong (I hate this but, yeah, I am never sure).

It's definitely possible, maybe not with recursion, but possible non theless.

[Mr_KoKa]

It's definitely possible, maybe not with recursion, but possible non theless.

I might get it wrong, then.

 

So for example let's have 8 bits:

00001011

 

Does function should return 3? If yes, how you can tell that there are 3 ones without checking every bit?

[79wjd]

I might get it wrong, then.

 

So for example let's have 8 bits:

00001011

 

Does function should return 3? If yes, how you can tell that there are 3 ones without checking every bit?

[Mr_KoKa]

I found this:
 

Find the number of bits in 10010111011111010101101110101111. (the answer's 22, for those of you keeping score.)break the word into 32 1-bit counters, pair, and add, to get 2-bit counters 1 0 0 1 0 1 1 0 0 0 1 1 1 1 1 1 =  1  0  0  1  0  1  1  0  0  0  1  1  1  1  1  1+0 1 1 1 1 1 1 1 1 1 0 1 0 0 1 1 =  0  1  1  1  1  1  1  1  1  1  0  1  0  0  1  1 ------------------------------- 1 1 1 2 1 2 2 1 1 1 1 2 1 1 2 2 = 01 01 01 10 01 10 10 01 01 01 01 10 01 01 10 10break the word into 16 2-bit counters, pair, and add, to get 4-bit counters 1 1 1 2 1 1 1 2 =   01   01   01   10   01   01   01   10+1 2 2 1 1 2 1 2 =   01   10   10   01   01   10   01   10 ---------------   --------------------------------------- 2 3 3 3 2 3 2 4 = 0010 0011 0011 0011 0010 0011 0010 0100break the word into 8 4-bit counters, pair, and add, to get 8-bit counters 3 3 3 4 =     0010     0011     0010     0010+2 3 2 2 =     0011     0011     0011     0100 -------   ----------------------------------- 5 6 5 6 = 00000101 00000110 00000101 00000110break the word into 4 8-bit counters, pair, and add, to get 16-bit counters  5  5 =         00000101         00000101+ 6  6 =         00000110         00000110 -----   --------------------------------- 11 11 = 0000000000001011 0000000000001011And finally, break the word into 2 16-bit counters, pair, and add, to get the answer, 22, in a single 32-bit counter. 11 =                 0000000000001011+11 =                 0000000000001011 --   -------------------------------- 22 = 00000000000000000000000000010110 

It is recursive but It's still ~31 operations.