C++ | Using Bit manipulation, Explained 100% !!
Using BitManipulation...\n\nWell, we have to concatente the binary presentation of a consective numbers; Okey that\'s all until now\nLet\'s create a new problem
Using BitManipulation...\n\nWell, we have to concatente the binary presentation of a consective numbers; Okey that\'s all until now\nLet\'s create a new problem using this problem which simple than this one instead of concatenting the the binary presentation Let\'s concatente the numbers their self :\nso for example **n = 9** so our numbers are **1, 2, 3, 4, 5, 6, 7, 8, 9** and we should get ***123456789***\nto do so :\nIt\'s simple **sum = 1**\nnext step we should get **12** : how would we do that ?? it\'s obvious that we should multiply the sum by 10 to be come 10 in this case then add our next number which is 2 to be become **sum = 12** (why we multiply by **10** ? we\'ll answer that lately)\n**sum = 12** and the next num is **3** so we should get **123** we do the same **sum = sum * 10** which will get us **sum = 120 **then add **3 **easily we will have **123**\nand so on until we get **123456789**\n```\n1-2 (e1) - 0\n0-0-3\n```\nto make this give us **123** it\'s obvious that we need to add 0 in (e1)\nOkey but the max number here is not 9\nos let\'s take **11** for example **(1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11)**\nwe should get **[123456789]1011** the **123456789** which is the part one, we already explained it what about **1011** how can we add it, so :\n**sum = 123456789**\n**for i = 10**\nshould we multiply by 10, Let\'s do so\n```\n1-2-3-4-5-6-7-8-9-0\n0-0-0-0-0-0-0-0-1-0\n................0-0 we can stop here obviously not our solution the number was ruined !!\n```\nI think we should reserve a two new places for the current number to get its place\nso We have something like :\n```\n1-2-3-4-5-6-7-8-9-0-0\n0-0-0-0-0-0-0-0-0-1-0\n```\nit\'s clear that we wil get our answer\nso here we multiply by 100 not 10\nif n = 120 when we\'ll reach 100 for **(100, 101, 102, ..., 120)** we should start to multiply by 1000 (3 zeroes = digit count) so we can handle digits count in number...\nit\'s simple we should start mult = 10\nso we can always do this until `i = mult then mult should be multiplied by 10 to become mult = 100`\nand so one when `i = mult again (mult = 100) mult *= 10` to become mult = 1000 so we can reserve three spots for the new number **(100 - 999)** and so on\nLet\'s go back to our problem, I think now it looks a little more simple !!!\nSo it\'s the same as decimal.... we should concatenate **12 and 13** we should reserve two empty spots (0) beside 12 for 13 means whe should multiply by 100 **(10 ^ (number of spots we need))**\nIn binary we have 1001 and 111 it\'s simple we just need to reserve 3 empty spots (0) for 111 beside 1001 so we should make 1001 become **[1001]000** then easly add **111** to have `[1001]111 := 1001111`\nso we need only to know the length of the number that we\'re gonna concatenate and reserve the spots for it\nin decimal we multiply to reserve spots but in binary we shoud shift right to reserve spot\n`12 and 13 :: 12 * 100 = 1200 `**(we got two empty spots = 2 trailing zeroes)** we add 13 to become **1213**\n`1001 and 111 ::: 1001 << 3` **(digits count in the number [111 in this case])** = 1001000 then add **111** to become **1001111** we will just add number in decimal system and surely that will what we get in binary presentation or if we did a binary addition opperation\nso **for n = 5** we have **1, 10, 11, 100, 101**\n**result = 0**\n**digit_count = 1**\nsign_that_digit_count_increased = 2 (means if we reach 2 than 2 - 3 numbers will have 2 digits, and so one `"{ i in [2 ^ n, 2 ^ (n + 1) - 1] ::: digits count of i is n }"`\n\nwe should do simply\n```\nfor i = 0 ------> n;\n\tif (i == sign_that_digit_count_increased)\n\t\tsign_that_digit_count_increased *= 2 (2 = 10(binary), 4 = 100(binary), 8 = 1000, 16 = 10000, 32 = 100000, ...)\n\t\tdigit_count += 1\n\tresult = result << digit_count (to reserve for the new number);\n\tresult += i;\n```\n\nor instead of " sign_that_digit_count_increased " we just have to check if (i & i + 1) is zero for example 100 and 11, 1000 and 111, 10000 and 1111; cause every consective numbers have at least one bit active commun between them expect (2 ^ n and 2 ^ n - 1) for every n\nI hope It\'s all clear\n\n```\nclass Solution {\npublic:\n    long long   sum = 0;\n    long long   MOD = 1000000007;\n\n    int concatenatedBinary(int n) {\n        int length_b = 0;\n        \n        for (int i=1; i<=n; i++)\n        {\n            if ((i & (i - 1)) == 0)\n                length_b++;\n            sum = ((sum << length_b) + i) % MOD;\n        }\n        return (sum);\n    }\n};\n```
['Bit Manipulation', 'C', 'C++']