Bit Twiddling Hacks in Batch

[aGerman]

We already have a math library, arithmetic functions, arrithmetic conditional operations, and probably some more threads about math.

Hereby I'll try to extend this collection with a function library which is more or less based on the C codes found at Bit Twiddling Hacks.

The actual library begins in line 300. The examples on top may give you an indication what they are good for and how to use them.

Code: Select all

@echo off &setlocal

call :get_int_min       &: get -2147483648 which can't be assigned directly

set /a "b1=0"           &: 00000000000000000000000000000000
set /a "b2=1"           &: 00000000000000000000000000000001
set /a "b3=14"          &: 00000000000000000000000000001110
set /a "b4=8"           &: 00000000000000000000000000001000
set /a "b5=10"          &: 00000000000000000000000000001010
set /a "b6=int_min"     &: 10000000000000000000000000000000
set /a "b7=-2147385343" &: 10000000000000011000000000000001
set /a "b8=-1"          &: 11111111111111111111111111111111


echo has_single_flag
call :has_single_flag b1 &&echo yes||echo no
call :has_single_flag b2 &&echo yes||echo no
call :has_single_flag b3 &&echo yes||echo no
call :has_single_flag b4 &&echo yes||echo no
call :has_single_flag b5 &&echo yes||echo no
call :has_single_flag b6 &&echo yes||echo no
call :has_single_flag b7 &&echo yes||echo no
call :has_single_flag b8 &&echo yes||echo no
echo(

echo has_any_flag
call :has_any_flag b1 &&echo yes||echo no
call :has_any_flag b2 &&echo yes||echo no
call :has_any_flag b3 &&echo yes||echo no
call :has_any_flag b4 &&echo yes||echo no
call :has_any_flag b5 &&echo yes||echo no
call :has_any_flag b6 &&echo yes||echo no
call :has_any_flag b7 &&echo yes||echo no
call :has_any_flag b8 &&echo yes||echo no
echo(

echo has_no_flag
call :has_no_flag b1 &&echo yes||echo no
call :has_no_flag b2 &&echo yes||echo no
call :has_no_flag b3 &&echo yes||echo no
call :has_no_flag b4 &&echo yes||echo no
call :has_no_flag b5 &&echo yes||echo no
call :has_no_flag b6 &&echo yes||echo no
call :has_no_flag b7 &&echo yes||echo no
call :has_no_flag b8 &&echo yes||echo no
echo(

echo has_all_flags
call :has_all_flags b1 &&echo yes||echo no
call :has_all_flags b2 &&echo yes||echo no
call :has_all_flags b3 &&echo yes||echo no
call :has_all_flags b4 &&echo yes||echo no
call :has_all_flags b5 &&echo yes||echo no
call :has_all_flags b6 &&echo yes||echo no
call :has_all_flags b7 &&echo yes||echo no
call :has_all_flags b8 &&echo yes||echo no
echo(

echo has_msb
call :has_msb b1 &&echo yes||echo no
call :has_msb b2 &&echo yes||echo no
call :has_msb b3 &&echo yes||echo no
call :has_msb b4 &&echo yes||echo no
call :has_msb b5 &&echo yes||echo no
call :has_msb b6 &&echo yes||echo no
call :has_msb b7 &&echo yes||echo no
call :has_msb b8 &&echo yes||echo no
echo(

echo has_lsb
call :has_lsb b1 &&echo yes||echo no
call :has_lsb b2 &&echo yes||echo no
call :has_lsb b3 &&echo yes||echo no
call :has_lsb b4 &&echo yes||echo no
call :has_lsb b5 &&echo yes||echo no
call :has_lsb b6 &&echo yes||echo no
call :has_lsb b7 &&echo yes||echo no
call :has_lsb b8 &&echo yes||echo no
echo(

echo has_all_of
call :has_all_of b1 "2|8" &&echo yes||echo no
call :has_all_of b2 "2|8" &&echo yes||echo no
call :has_all_of b3 "2|8" &&echo yes||echo no
call :has_all_of b4 "2|8" &&echo yes||echo no
call :has_all_of b5 "2|8" &&echo yes||echo no
call :has_all_of b6 "2|8" &&echo yes||echo no
call :has_all_of b7 "2|8" &&echo yes||echo no
call :has_all_of b8 "2|8" &&echo yes||echo no
echo(

echo has_any_of
call :has_any_of b1 "2|8" &&echo yes||echo no
call :has_any_of b2 "2|8" &&echo yes||echo no
call :has_any_of b3 "2|8" &&echo yes||echo no
call :has_any_of b4 "2|8" &&echo yes||echo no
call :has_any_of b5 "2|8" &&echo yes||echo no
call :has_any_of b6 "2|8" &&echo yes||echo no
call :has_any_of b7 "2|8" &&echo yes||echo no
call :has_any_of b8 "2|8" &&echo yes||echo no
echo(

echo has_at_index
call :has_at_index b1 2 &&echo yes||echo no
call :has_at_index b2 2 &&echo yes||echo no
call :has_at_index b3 2 &&echo yes||echo no
call :has_at_index b4 2 &&echo yes||echo no
call :has_at_index b5 2 &&echo yes||echo no
call :has_at_index b6 2 &&echo yes||echo no
call :has_at_index b7 2 &&echo yes||echo no
call :has_at_index b8 2 &&echo yes||echo no
echo(

echo has_none_of
call :has_none_of b1 "2|8" &&echo yes||echo no
call :has_none_of b2 "2|8" &&echo yes||echo no
call :has_none_of b3 "2|8" &&echo yes||echo no
call :has_none_of b4 "2|8" &&echo yes||echo no
call :has_none_of b5 "2|8" &&echo yes||echo no
call :has_none_of b6 "2|8" &&echo yes||echo no
call :has_none_of b7 "2|8" &&echo yes||echo no
call :has_none_of b8 "2|8" &&echo yes||echo no
echo(

echo not_at_index
call :not_at_index b1 2 &&echo yes||echo no
call :not_at_index b2 2 &&echo yes||echo no
call :not_at_index b3 2 &&echo yes||echo no
call :not_at_index b4 2 &&echo yes||echo no
call :not_at_index b5 2 &&echo yes||echo no
call :not_at_index b6 2 &&echo yes||echo no
call :not_at_index b7 2 &&echo yes||echo no
call :not_at_index b8 2 &&echo yes||echo no
echo(

echo count_flags
call :count_flags b1
echo %errorlevel%
call :count_flags b2
echo %errorlevel%
call :count_flags b3
echo %errorlevel%
call :count_flags b4
echo %errorlevel%
call :count_flags b5
echo %errorlevel%
call :count_flags b6
echo %errorlevel%
call :count_flags b7
echo %errorlevel%
call :count_flags b8
echo %errorlevel%
echo(

echo get_lowest
call :get_lowest b1 flag
echo %flag%
call :get_lowest b2 flag
echo %flag%
call :get_lowest b3 flag
echo %flag%
call :get_lowest b4 flag
echo %flag%
call :get_lowest b5 flag
echo %flag%
call :get_lowest b6 flag
echo %flag%
call :get_lowest b7 flag
echo %flag%
call :get_lowest b8 flag
echo %flag%
echo(

echo get_highest
call :get_highest b1 flag
echo %flag%
call :get_highest b2 flag
echo %flag%
call :get_highest b3 flag
echo %flag%
call :get_highest b4 flag
echo %flag%
call :get_highest b5 flag
echo %flag%
call :get_highest b6 flag
echo %flag%
call :get_highest b7 flag
echo %flag%
call :get_highest b8 flag
echo %flag%
echo(

echo flag_to_index
call :flag_to_index 8
echo %errorlevel%
echo(

echo index_to_flag
call :index_to_flag 31 flag
echo %flag%
echo(

echo set_all_of
call :set_all_of b5 "1|4"
echo %b5%
echo(

echo clear_all_of
call :clear_all_of b5 "1|4"
echo %b5%
echo(

echo set_at_index
call :set_at_index b5 0
echo %b5%
echo(

echo clear_at_index
call :clear_at_index b5 0
echo %b5%
echo(

echo clear_lowest
call :clear_lowest b3
echo %b3%
echo(

echo clear_highest
call :clear_highest b3
echo %b3%
echo(

echo flip_all_of
call :flip_all_of b5 "2|4"
echo %b5%
call :flip_all_of b5 "2|4"
echo %b5%
echo(

echo flip_at_index
call :flip_at_index b5 2
echo %b5%
call :flip_at_index b5 2
echo %b5%
echo(

echo pull_next_flag
setlocal EnableDelayedExpansion
set /a "bitset=b5"
echo * %bitset% *
call :count_flags bitset
for /l %%i in (1 1 %errorlevel%) do (
  call :pull_next_flag bitset flag
  echo   !flag!
)
set /a "bitset=b6"
echo * %bitset% *
call :count_flags bitset
for /l %%i in (1 1 %errorlevel%) do (
  call :pull_next_flag bitset flag
  echo   !flag!
)
set /a "bitset=b7"
echo * %bitset% *
call :count_flags bitset
for /l %%i in (1 1 %errorlevel%) do (
  call :pull_next_flag bitset flag
  echo   !flag!
)
set /a "bitset=b8"
echo * %bitset% *
call :count_flags bitset
for /l %%i in (1 1 %errorlevel%) do (
  call :pull_next_flag bitset flag
  echo   !flag!
)
endlocal
echo(

echo logical_shift_right
echo * %b6% *
call :logical_shift_right b6 1
echo   %b6%
echo * %b8% *
call :logical_shift_right b8 1
echo   %b8%
echo(

pause
exit /b









:: Terminology used:
:: bitset - a set of 32 bits represented by a signed integer in two's complement (that's just the only numeric type which the cmd supports)
:: flag   - one bit at a certain position in the bitset which represets a value of a power of two with exponent 0..31 if the bit itself has a value of 1, or 0 if the bit has a value of 0
:: index  - zero based index of a bit in the bitset that represents the flag, it also represents the exponent of the power of two of the flag's value (log2)
:: has_   - returns a boolean in errorlevel logic (0 means true, 1 means false)
:: get_   - publish the value of a flag
:: set_   - turn the bit belonging to the flag into 1, regardless of its original value
:: clear_ - turn the bit belonging to the flag into 0, regardless of its original value
:: flip_  - toggle the value of the bit belonging to the flag from 0 to 1 and from 1 to 0 respectively
:: pull_  - get the value of a flag and clear it in the bitset
:: ref_   - parameter marked to expect an argument passed by reference - that is, a variable name has to be passed rather than a value because its value will be updated
:: Also prefer passing by reference of the other arguments if there is any risk to pass -2147483648 by value.
:: An argument for flags might be already precomposed to a bitmask, or passed as list of flags separated with | operators.
:: Surrounding quotation marks are mandatory if the arguments contain terms with special characters or token delimiters.

::::::::::::::::::::::::::::::::: work around assigning -2147483648 ::::::::::::::::::::::::::::::::

:get_int_min [ref_var]
:: defines either variable int_min or the optionally passed variable name with -2147483648 which can't be assigned directly
if "%~1"=="" (set /a "int_min=~2147483647") else set /a "%~1=~2147483647"
exit /b %errorlevel%


::::::::::::::::::::::::::::::::::::::::::: not modifying ::::::::::::::::::::::::::::::::::::::::::

:has_single_flag "bitset"
:: returns 0 if exactly one flag is set (that is, bitset is a power of two with exponent 0..31)
setlocal DisableDelayedExpansion
set /a "e=!(%~1)|!!((%~1)&((%~1)-1))"
endlocal&exit /b %e%

:has_any_flag "bitset"
:: returns 0 if at least one flag is set (that is, bitset is not 0)
setlocal DisableDelayedExpansion
set /a "e=!(%~1)"
endlocal&exit /b %e%

:has_no_flag "bitset"
:: returns 0 if no flag is set (that is, bitset is 0)
setlocal DisableDelayedExpansion
set /a "e=!!(%~1)"
endlocal&exit /b %e%

:has_all_flags "bitset"
:: returns 0 if all flags are set (that is, bitset is -1)
setlocal DisableDelayedExpansion
set /a "e=!!~(%~1)"
endlocal&exit /b %e%

:has_msb "bitset"
:: returns 0 if the most significant bit is set (that is, bitset is a negative value)
setlocal DisableDelayedExpansion
set /a "e=!((%~1)>>31)"
endlocal&exit /b %e%

:has_lsb "bitset"
:: returns 0 if the least significant bit is set (that is, bitset is an odd value)
setlocal DisableDelayedExpansion
set /a "e=!((%~1)&1)"
endlocal&exit /b %e%

:has_all_of "bitset" "flag_1[|flag_2[|...[|flag_n]]]"
:: returns 0 if bitset contains all of the specified flags
setlocal DisableDelayedExpansion
set /a "e=!!(((%~1)&(%~2))-(%~2))"
endlocal&exit /b %e%

:has_any_of "bitset" "flag_1[|flag_2[|...[|flag_n]]]"
:: returns 0 if bitset contains at least one of the specified flags
setlocal DisableDelayedExpansion
set /a "e=!((%~1)&(%~2))"
endlocal&exit /b %e%

:has_at_index "bitset" "index"
:: returns 0 if the flag is set at the specified index
setlocal DisableDelayedExpansion
set /a "e=!((%~1)&(1<<(%~2)))"
endlocal&exit /b %e%

:has_none_of "bitset" "flag_1[|flag_2[|...[|flag_n]]]"
:: returns 0 if bitset contains none of the specified flags
setlocal DisableDelayedExpansion
set /a "e=!!((%~1)&(%~2))"
endlocal&exit /b %e%

:not_at_index "bitset" "index"
:: returns 0 if the flag is 0 at the specified index
setlocal DisableDelayedExpansion
set /a "e=!!((%~1)&(1<<(%~2)))"
endlocal&exit /b %e%

:count_flags "bitset" [ref_num]
:: returns the number of set flags, optionally also assigns it to the variable name passed as second argument
setlocal DisableDelayedExpansion
set /a "b=(%~1)-(((%~1)>>1)&1431655765),b=(b&858993459)+((b>>2)&858993459),c=((b+(b>>4)&252645135)*16843009)>>24"
endlocal&(if "%~2" neq "" set "%~2=%c%")&exit /b %c%

:get_lowest "bitset" ref_flag
:: assigns the lowest set flag to the variable name passed as second argument
set /a "%~2=(%~1)&-(%~1)"
exit /b %errorlevel%

:get_highest "bitset" ref_flag
:: assigns the highest set flag to the variable name passed as second argument
set /a "%~2=(%~1)|((%~1)>>1),%~2|=%~2>>2,%~2|=%~2>>4,%~2|=%~2>>8,%~2|=%~2>>16,%~2-=(%~2>>1)&2147483647"
exit /b %errorlevel%

:flag_to_index "flag" [ref_index]
:: returns the zero-based index of a flag in a 32 bit integer where the flag must be a power of two with exponent 0..31, optionally also assigns it to the variable name passed as second argument
setlocal DisableDelayedExpansion
set /a "i=!!((%~1)&-1431655766),i|=(!!((%~1)&-65536))<<4,i|=(!!((%~1)&-16711936))<<3,i|=(!!((%~1)&-252645136))<<2,i|=(!!((%~1)&-858993460))<<1"
endlocal&(if "%~2" neq "" set "%~2=%i%")&exit /b %i%

:index_to_flag "index" ref_flag
:: assigns the power of two with exponent passed as index (0..31) to the variable name passed as second argument
set /a "%~2=1<<(%~1)"
exit /b %errorlevel%


::::::::::::::::::::::::::::::::::::::::::::: modifying ::::::::::::::::::::::::::::::::::::::::::::

:set_all_of ref_bitset "flag_1[|flag_2[|...[|flag_n]]]"
:: takes the variable name of the bitset, and sets the specified flags in the bitset
set /a "%~1|=(%~2)"
exit /b %errorlevel%

:set_at_index ref_bitset "index"
:: takes the variable name of the bitset, and sets the flag at the specified index
set /a "%~1|=1<<(%~2)"
exit /b %errorlevel%

:clear_all_of ref_bitset "flag_1[|flag_2[|...[|flag_n]]]"
:: takes the variable name of the bitset, and updates the specified flags to 0
set /a "%~1&=~(%~2)"
exit /b %errorlevel%

:clear_at_index ref_bitset "index"
:: takes the variable name of the bitset, and updates the flag at the specified index to 0
set /a "%~1&=~(1<<(%~2))"
exit /b %errorlevel%

:clear_lowest ref_bitset
:: takes the variable name of the bitset, and updates the lowest set flag to 0
set /a "%~1=%~1&(%~1-1)"
exit /b %errorlevel%

:clear_highest ref_bitset
:: takes the variable name of the bitset, and updates the highest set flag to 0
setlocal DisableDelayedExpansion
set /a "f=%~1|(%~1>>1),f|=f>>2,f|=f>>4,f|=f>>8,f|=f>>16,f-=(f>>1)&2147483647,b=%~1&(f-1)"
endlocal&set "%~1=%b%"&exit /b %errorlevel%

:flip_all_of ref_bitset "flag_1[|flag_2[|...[|flag_n]]]"
:: takes the variable name of the bitset, and flips the specified flags in the bitset
set /a "%~1^=(%~2)"
exit /b %errorlevel%

:flip_at_index ref_bitset "index"
:: takes the variable name of the bitset, and flips the flag at the specified index
set /a "%~1^=1<<(%~2)"
exit /b %errorlevel%

:pull_next_flag ref_bitset ref_flag
:: takes the variable name of the bitset, assigns the lowest set flag to the variable name passed as second argument, and updates the found flag to 0
set /a "%~2=%~1&-%~1,%~1=%~1&(%~1-1)"
exit /b %errorlevel%

:logical_shift_right ref_bitset "positions"
:: takes the variable name of the bitset, and shifts flags the specified number of positions to the right while zeros are shifted in to the left
set /a "%~1=(%~1>>(%~2))&(((2147483647>>(%~2))<<1)|1)"
exit /b %errorlevel%

Actually bitwise operations are incredibly fast. If you execute the test code you won't observe the potential performance though.
The first reason is that the code is quite long. Calling labels is expensive and is getting even worse the more lines a code has.
The second reason is that I try to leave the environment unchanged and to work around side effects of the logical NOT operator (!) in an environment with enabled delayed variable expansion. SETLOCAL internally triggers the creation of a stack with copies of the environment. This is slow, too.
Thus, this library is not necessarily meant to be used as such. The core of each of these functions is a single SET /A statement. Just take it out and include it in your code wherever you need the operation.

Maybe you are wondering for what these operations are useful and why I thought it was worth to open this topic.
I'll give you two examples below ...


Steffen

[aGerman]

If you ever used ROBOCOPY and you observed the errorlevel it returns, then you might have seen that it can have 17 different values. This seems to be confusing. But in reality it's quite simple because it's a bitset with only 5 bits used. Each of these 5 bits is a flag indicating a single information. See ROBOCOPY Exit Codes.
Now that you know it, you can count the flags set (see :count_flags), pull them out separately (see :pull_next_flag), and print the related information.
In this example I simulate some possible conditions in order to trigger different exit codes. The messages related to the flags are defined at the early beginning of the code. The :process_robocopy_return_code function contains the required operations.

rcpy.bat

Code: Select all

@echo off &setlocal EnableDelayedExpansion
set "msg0=No errors occurred, and no copying was done. The source and destination directory trees are completely synchronized."
set "msg1=One or more files were copied successfully (that is, new files have arrived)."
set "msg2=Some Extra files or directories were detected. Examine the output log. Some housekeeping may be needed."
set "msg4=Some Mismatched files or directories were detected. Examine the output log. Housekeeping is probably necessary."
set "msg8=Some files or directories could not be copied (copy errors occurred and the retry limit was exceeded). Check these errors further."
set "msg16=Serious error. Robocopy did not copy any files. This is either a usage error or an error due to insufficient access privileges on the source or destination directories."

2>nul rd /s /q "%temp%\rbcpy_test"


echo   ~~~~~~~~~~~~~~&echo   ### TEST 1 ###&echo   ~~~~~~~~~~~~~~
md "%temp%\rbcpy_test\original\a1\a2"
>"%temp%\rbcpy_test\original\a1\test1.txt" type nul
>"%temp%\rbcpy_test\original\a1\test2.txt" type nul
robocopy "%temp%\rbcpy_test\original" "%temp%\rbcpy_test\duplicate" /s /e /r:0 /w:0
echo(&echo   ### errorlevel: %errorlevel% ###
call :process_robocopy_return_code %errorlevel%
pause

cls&echo   ~~~~~~~~~~~~~~&echo   ### TEST 2 ###&echo   ~~~~~~~~~~~~~~
robocopy "%temp%\rbcpy_test\original" "%temp%\rbcpy_test\duplicate" /s /e /r:0 /w:0
echo(&echo   ### errorlevel: %errorlevel% ###
call :process_robocopy_return_code %errorlevel%
pause

cls&echo   ~~~~~~~~~~~~~~&echo   ### TEST 3 ###&echo   ~~~~~~~~~~~~~~
>"%temp%\rbcpy_test\original\a1\test3.txt" type nul
md "%temp%\rbcpy_test\duplicate\a1\test3.txt"
robocopy "%temp%\rbcpy_test\original" "%temp%\rbcpy_test\duplicate" /s /e /r:0 /w:0
echo(&echo   ### errorlevel: %errorlevel% ###
call :process_robocopy_return_code %errorlevel%
pause

cls&echo   ~~~~~~~~~~~~~~&echo   ### TEST 4 ###&echo   ~~~~~~~~~~~~~~
del "%temp%\rbcpy_test\original\a1\test2.txt"
robocopy "%temp%\rbcpy_test\original" "%temp%\rbcpy_test\duplicate" /s /e /r:0 /w:0
echo(&echo   ### errorlevel: %errorlevel% ###
call :process_robocopy_return_code %errorlevel%
pause

cls&echo   ~~~~~~~~~~~~~~&echo   ### TEST 5 ###&echo   ~~~~~~~~~~~~~~
>"%temp%\rbcpy_test\original\a1\test1.txt" echo foo
>"%temp%\rbcpy_test\original\a1\test4.txt" type nul
3>"%temp%\rbcpy_test\duplicate\a1\test1.txt" (
  robocopy "%temp%\rbcpy_test\original" "%temp%\rbcpy_test\duplicate" /s /e /r:0 /w:0
  echo(&echo   ### errorlevel: !errorlevel! ###
  call :process_robocopy_return_code !errorlevel!
)
pause

cls&echo   ~~~~~~~~~~~~~~&echo   ### TEST 6 ###&echo   ~~~~~~~~~~~~~~
robocopy foo
echo(&echo   ### errorlevel: %errorlevel% ###
call :process_robocopy_return_code %errorlevel%
pause


rd /s /q "%temp%\rbcpy_test"
exit /b



:process_robocopy_return_code errorlevel_value
if %~1==0 echo - %msg0%&exit /b
setlocal EnableDelayedExpansion
set /a "bitset=%~1,b=(%~1)-(((%~1)>>1)&1431655765),b=(b&858993459)+((b>>2)&858993459),count=((b+(b>>4)&252645135)*16843009)>>24"
for /l %%c in (1 1 %count%) do (
  set /a "flag=bitset&-bitset,bitset=bitset&(bitset-1)"
  for %%f in (!flag!) do echo - !msg%%f!
)
endlocal &exit /b

[aGerman]

Completely different task - solve a Sudoku puzzle.

This is tricky. There are algorithms to find the number using pure logic. But that way you would have to apply a lot of different algorithms and still some patterns are not solvable using logic only. You still would need to use brute force. Brute force and slow Batch don't fit together you say? True. If you only try all possible combinations it would take ages. But there is a good algorithm for Sudoku puzzles called Backtracking. Have a look at the Wikipedia entry and you'll see how it works. The GIF in the examples is a nice demonstration.

This is a Sudoku grid which is said to have a rather high degree of difficulty for the Backtracking algorithm:
grid.txt

Code: Select all

100034080
000800500
004060021
018000000
300102006
000000810
520070900
006009000
090640002

As you can see it consists of 9 lines with 9 numbers 1..9 each. Values to be found are set to 0.

The code I developed to solve grids like that:
sudoku.bat

Code: Select all

@echo off&setlocal
set "source=grid.txt"
set "target=con"

setlocal EnableDelayedExpansion&echo ### %time% ###
set "first_0="&set /a "ns[1]=1,ns[2]=2,ns[4]=3,ns[8]=4,ns[16]=5,ns[32]=6,ns[64]=7,ns[128]=8,ns[256]=9,fs[1]=1,fs[2]=2,fs[3]=4,fs[4]=8,fs[5]=16,fs[6]=32,fs[7]=64,fs[8]=128,fs[9]=256"
for /l %%i in (0 1 8) do set /a "rset[%%i]=-512,cset[%%i]=-512,bset[%%i]=-512"
for %%a in (0 1 2) do for %%b in (0 1 2) do for %%c in (0 1 2) do for %%d in (0 1 2) do set /a "x=%%a*3+%%c,y=%%b*3+%%d,z=x*9+y,i=x*9+y,j=y*9+x"&set /a "v[!i!].ri=x,v[!j!].ci=x,v[!z!].bi=%%a*3+%%b"
<"!source!" (for /l %%r in (0 1 8) do (set "ln="&set /p "ln="&for /l %%c in (0 1 8) do (
  set /a "i=%%r*9+%%c,n=!ln:~%%c,1!"&if !n!==0 (if not defined first_0 (set /a "first_0=i,last_i=i") else set /a "next_0[!last_i!]=i,last_i=i")
  set /a "ri=v[!i!].ri,ci=v[!i!].ci,bi=v[!i!].bi"&set /a "v[!i!].n=n,rset[!ri!]|=fs[!n!],cset[!ci!]|=fs[!n!],bset[!bi!]|=fs[!n!]"))&set /a "next_0[!last_i!]=-1")
call :solve %first_0%&&echo No solution found.||<nul >"!target!" (for /l %%r in (0 1 8) do (for /l %%c in (0 1 8) do set /a "i=%%r*9+%%c"&for %%i in (!i!) do set /p "=!v[%%i].n!")&echo()
echo ### %time% ###&pause&exit /b
:solve
set /a "inv[%1]=~(rset[!v[%1].ri!]|cset[!v[%1].ci!]|bset[!v[%1].bi!]),d=inv[%1]-((inv[%1]>>1)&1431655765),d=(d&858993459)+((d>>2)&858993459),cnt=((d+(d>>4)&252645135)*16843009)>>24"
(for /l %%c in (1 1 !cnt!) do (
  set /a "f[%1]=inv[%1]&-inv[%1],inv[%1]=inv[%1]&(inv[%1]-1),rset[!v[%1].ri!]|=f[%1],cset[!v[%1].ci!]|=f[%1],bset[!v[%1].bi!]|=f[%1]"
  if !next_0[%1]!==-1 (call) else call :solve !next_0[%1]!
  if errorlevel 1 (set /a "v[%1].n=ns[!f[%1]!]"&exit /b 1) else set /a "rset[!v[%1].ri!]&=~f[%1],cset[!v[%1].ci!]&=~f[%1],bset[!v[%1].bi!]&=~f[%1]"))&exit /b 0

This code solves the above grid in ~20s on my fast machine at work and ~90s on my slow netbook at home.

I have to apologize for the bad readability. The code calls function :solve recursively. And as always in Batch, the time it takes to find labels in the script is depending on the number of lines the code has. Thus, I had to compress it for performance reasons. Fast calculations don't help if you loose too much speed due to Batch deficiencies.
But I don't want to leave you without some explanations.
There is a values array v[0..80]. These variable names exist four times with different appendixes: .n (1..9, or 0 for "empty") for the actual number, .ri for the row index (0..8 ) the value belongs to, .ci for the column index (0..8 ), and .bi for the box index (0..8 ). This figure shows the indexes:

Code: Select all

                                          COLUMNS
         0        1        2        3        4        5        6        7        8
    +========+========+========+========+========+========+========+========+========+
    I        :        :        I        :        :        I        :        :        I
  0 I    0   :    1   :    2   I    3   :    4   :    5   I    6   :    7   :    8   I
    I        :        :        I        :        :        I        :        :        I
    +--------+--------+--------+--------+--------+--------+--------+--------+--------+
    I        :        :        I        :        :        I        :        :        I
  1 I    9   :   10   :   11   I   12   :   13   :   14   I   15   :   16   :   17   I
    I        : BOX  0 :        I        : BOX  1 :        I        : BOX  2 :        I
    +--------+--------+--------+--------+--------+--------+--------+--------+--------+
    I        :        :        I        :        :        I        :        :        I
  2 I   18   :   19   :   20   I   21   :   22   :   23   I   24   :   25   :   26   I
    I        :        :        I        :        :        I        :        :        I
    +========+========+========+========+========+========+========+========+========+
    I        :        :        I        :        :        I        :        :        I
  3 I   27   :   28   :   29   I   30   :   31   :   32   I   33   :   34   :   35   I
    I        :        :        I        :        :        I        :        :        I
    +--------+--------+--------+--------+--------+--------+--------+--------+--------+
R   I        :        :        I        :        :        I        :        :        I
O 4 I   36   :   37   :   38   I   39   :   40   :   41   I   42   :   43   :   44   I
W   I        : BOX  3 :        I        : BOX  4 :        I        : BOX  5 :        I
S   +--------+--------+--------+--------+--------+--------+--------+--------+--------+
    I        :        :        I        :        :        I        :        :        I
  5 I   45   :   46   :   47   I   48   :   49   :   50   I   51   :   52   :   53   I
    I        :        :        I        :        :        I        :        :        I
    +========+========+========+========+========+========+========+========+========+
    I        :        :        I        :        :        I        :        :        I
  6 I   54   :   55   :   56   I   57   :   58   :   59   I   60   :   61   :   62   I
    I        :        :        I        :        :        I        :        :        I
    +--------+--------+--------+--------+--------+--------+--------+--------+--------+
    I        :        :        I        :        :        I        :        :        I
  7 I   63   :   64   :   65   I   66   :   67   :   68   I   69   :   70   :   71   I
    I        : BOX  6 :        I        : BOX  7 :        I        : BOX  8 :        I
    +--------+--------+--------+--------+--------+--------+--------+--------+--------+
    I        :        :        I        :        :        I        :        :        I
  8 I   72   :   73   :   74   I   75   :   76   :   77   I   78   :   79   :   80   I
    I        :        :        I        :        :        I        :        :        I
    +========+========+========+========+========+========+========+========+========+

Just an example: The value with index 32 belongs to row 3, column 5, and box 4.

Indexes are constant and thus, we initialize them at the early beginning.
Further we have an array of bitsets for the rows (rset[0..8]), the columns (cset[0..8]), and the boxes (bset[0..8]). They are initialized with -512. In binary this value is
11111111111111111111111000000000
The 9 low order bits are 0. They are used to represent the numbers in the row, column, or box. The least significant bit is for number 1, the second for number 2, etc.
Two additional arrays are initialized. ns[] to translate flags to numbers, and fs[] to translate numbers to flags.

While reading the Sudoku grid, the positions of the zeros are saved in an array (next_0[]), and the flags of the row, column, and box the read number belongs to are updated. That is, the flag that belongs to the number is translated using the fs[] array, and is getting set in the bitsets using the | operator.
Believe it or not - the indexes of the zero ("empty") values and the flags in the bitsets is all that you need to solve the Sudoku puzzle. The numbers are completely out of interest once the grid has been read from the file.
To calculate the missing values we call the :solve function and pass the index of the first zero value in the grid.
Now we want to check wich flags have not been set for the row, column, and box a number belongs to. First we merge these flags using bitwise OR. E.g. ...

Code: Select all

      unused bits <|< 9 used bits
  ... 1 1 1 1 1 1 1 1 1 1 0 0 1 1 0 0  row flags with bits 3, 4, 7, 8, 9 set
| ... 1 1 1 1 1 1 1 1 0 1 0 0 0 0 1 1  column flags with bits 1, 2, 7, 9 set
| ... 1 1 1 1 1 1 1 0 1 0 0 0 1 1 1 1  box flags with bits 1, 2, 3, 4, 8 set
-------------------------------------
  ... 1 1 1 1 1 1 1 1 1 1 0 0 1 1 1 1  merged flags with bits 1, 2, 3, 4, 7, 8, 9 set

As you can see, flags for 5 and 6 are still 0. These are the candidates we have to try out.

We invert the merged flags using bitwise NOT.

Code: Select all

      unused bits <|< 9 used bits
~ ... 1 1 1 1 1 1 1 1 1 1 0 0 1 1 1 1  merged flags
-------------------------------------
  ... 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0  inverted flags

Now we count the flags (see :count_flags function), then we pull each flag in a FOR /L loop (see :pull_next_flag function).
The first found flag is set in the related bitsets and the :solve function is called recursively with the index of the next zero value. This produces a call stack. If a certain value doesn't solve the Sudoku, we move down the call stack, reset the changed bitsets to their former values, and try with the next possible candidate out of the inverted flags. Once the Sudoku was solved, the related numbers are assigned to the .n values while moving down the call stack. They are translated (using ns[]) from the flag tried in the latest recursion on every level of the call stack. After that the solved Sudoku can be printed out.
The maximum height of the call stack equals the number of zeros in the original grid + 1. This hight will be reached if the Sudoku has been solved but never before. In the mean time the call stack will be crawled up and down thousands of times until the right values have been found. This takes a lot of time in Batch. And only the fact that bitwise operations are fast and you can execute several at once (in a single SET /A statement) makes Backtracking even a reasonable algorithm.

[Aacini]

Mmmm... These are my thoughts...

Binary numbers and binary arithmetic is a tool that allows to perform arithmetic operations in a much efficient way than decimal operations, so is the right tool when speed is important in an application. Binary numeral system also allows to solve a problem in a much simpler way when the problem can be expressed in terms of bits instead of decimal numbers. However, as any tool, it should be learned in order to use it correctly. IMHO have no much sense to write subroutines or functions that allows to use binary numbers in an "easy" (decimal-like) way because in such a case the speed gain of binary operations is lost in the subroutine call. I think that binary operations should be directly used in the arithmetic expressions...

An example of a not so good use of binary numbers is precisely your ROBOCOPY example! You used a complicated (decimal) formula in order to convert the errorlevel value in 1-16 range into discrete 1,2,4,8,16 values. This is the way I would do it:

Code: Select all

:process_robocopy_return_code errorlevel_value
if %~1==0 echo - %msg0%&exit /b
setlocal EnableDelayedExpansion
for /L %%b in (0,1,4) do (
   set /A "flag = 1<<%%b & %~1"
   if !flag! neq 0 for %%f in (!flag!) do echo - !msg%%f!
)
endlocal &exit /b

That is, use a FOR to vary the index of the bit from 0 to 4. Then move a bit with a 1 to such a position via a SHL (shift-left: <<) operation. Finally, a simple AND of this value gives the (decimal) discrete value of the flag at such a position...



I used a similar approach of binary operations in the last version of my VIBORAS.bat: A multi-player version in color of Snake game. This is a summary of the relevant parts about the binary numeral scheme used in VIBORAS.bat game:

This program was developed with the goal of made the code and logic as short as possible, making good use of complex data structures. These are the relevant points in the program design:

The maximum size for the board is: width=128 and height=63. Board positions are managed in a single number with both coordinates combined: horizontal coordinate in bits 6..0 (7 bits: 0-127 range) and vertical coordinate in bits 12..7 (6 bits: 0-63 range), as shown in this scheme:

Code: Select all

Coordinates:     VerticalHorizontal
Bits:             12....76.....0      Vertical: 6 bits, Horizontal: 7 bits
Last position:     1111101111111      Vertical=62, Horizontal=127
Hexadecimal:       1   F   7   F      Decimal=8063

This means that all board positions can be represented by a single number in the 0..8063 range. The first board position, at coordinates (0,0), is represented by number 0. The last board position, at coordinates (127,62), is represented by number 8063 as shown in previous scheme. The conversions formulae are: SET /A "position=(row<<7)+col" and SET /A "row=position>>7, col=position%%128".

The contents of all positions in the board are stored in a string with up to 8064 characters...

The representation of a position in a single number allows to move it using just one operation, instead of two separate operations for ROW and COL parts. The four possible movements are +- 1 for horizontal coordinate, and +- 1<<7 (128) for vertical coordinate: SET /A "toRight=1, toLeft=-1, toDown=128, toUp=-128". This also means that any distance between two positions in the same line or row can be stored as a single number that includes the direction (vector). For example, 5 means "5 positions to right", -10 is "10 positions to left", 1280 is "10 positions to down", etc.

Snake movement is managed via four variables: headPos, headMov, tailPos and tailMov; these variables contain single numbers as explained before. The snake can be moved in a single operation in this way: SET /A "headPos+=headMov, tailPos+=tailMov".

The complete description of the scheme is given at chapter 8 of VIBORAS.bat User's Manual.

Antonio

[aGerman]

You used a complicated (decimal) formula in order to convert the errorlevel value in 1-16 range into discrete 1,2,4,8,16 values.

I agree that it might not make much sense if you only process the 5 low order bits. But it's not exactly as you think. The "magic" decimal values are bit patterns. (Use the Windows calculator, set the style to "Programmer", switch the type size to "DWORD", and copy the values into the calculator window. The binary expressions will give you an indication of how it works.) They are used to count the flags set. This number is used in the FOR /L loop which doesn't run always 5 iterations, but only as many iterations as flags are set. The previous counting is necessary due to the lack of a WHILE loop in Batch. (Something that Carlos worked around in the Enhanced Batch project btw.)

Your concerns about decimal calculations are valid for things like division or modulus. Addition and subtraction are just single CPU operations. Multiplication is cheap, too.

I used a similar approach of binary operations

Yes, that's another good example. Thanks for adding the reference to this code!

Steffen

[Eureka!]

Your concerns about decimal calculations are valid for things like division or modulus. Addition and subtraction are just single CPU operations. Multiplication is cheap, too.

How do you know? Is there a thread about that on these forums? (still 7000+ topics to read ...)

I did some quick tests and those support your statements:

Code: Select all

set errcode=19

if %errcode% == 0 echo ERROR 0: %msg0% & exit /b
for %%i in (1 2 4 8 16)  do (
  set /a "check=%errcode% & %%i"
  if !check! == %%i echo ERROR %%i: !msg%%i!
)

is about as fast as the one @Aacini posted (both with output redirected to nul).
And

Code: Select all

for /l %%i in (1,1,100000) do set /a "z=67586768 & (1|2|4|8|16|32|64|128|256|512|1024|2048)

is exactly as fast as

Code: Select all

for /l %%i in (1,1,100000) do set /a "z=67586768 & (1+2+4+8+16 +32+64+128+256+512+1024+2048)

(that works because the first one is a bitmask; no overlap)


I could write this at every other post on this forum, but my respect for the Sudoku solver. Unbelievable!

[aGerman]

How do you know? Is there a thread about that on these forums? (still 7000+ topics to read ...)

No, this is not a subject of this forum. You will find the information somewhere in the depth of the internet. Can't remember where I read it, it's too long ago already.

Batch is an interpreted language where everything is text in the first place. Even numeric strings have to be parsed and converted to a numeric value before they can be used for calculations internally. Thus, Aacini is still entirely right if you treat "complicated formula" as "long formula" where the string has to be parsed, tokenized, and substrings have to be converted. Eventually that may take more time than the actual calculation afterwards.

Steffen